服务器之家

服务器之家 > 正文

单链表实现反转的3种方法示例代码

时间:2021-07-21 15:07     来源/作者:攻城猿bilibili

前言

单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案:

1 ,两两对换

2, 放入数组,倒置数组

3, 递归实现

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
 
 int data;
 struct Node *pnext;
 
 
} Node,*pnode;
pnode CreateNode()
{
 
 pnode phead=(pnode)malloc(sizeof(Node));
 if(phead==NULL)
 {
  printf("fail to allocate memory");
  return -1;
 }
 phead->pnext=NULL;
 int n;
 pnode ph=phead;
 for(int i=0; i<5; i++)
 {
 
  pnode p=(pnode)malloc(sizeof(Node));
  if(p==NULL)
  {
   printf("fail to allocate memory");
   return -1;
  }
  p->data=(i+2)*19;
  phead->pnext=p;
  p->pnext=NULL;
  phead=phead->pnext;
 
 
 }
 return ph;
}
int list(pnode head)
{
 int count=0;
 printf("遍历结果: ");
 while(head->pnext!=NULL)
 {
  printf("%d ",head->pnext->data);
  head=head->pnext;
  count++;
 }
 printf("链表长度为:%d ",count);
 return count;
}
pnode reverse2(pnode head)//两两节点之间不断交换
{
 if(head == NULL || head->next == NULL)
 return head;
 pnode pre = NULL;
 pnode next = NULL;
 while(head != NULL){
  next = head->next;
  head->next = pre;
  pre = head;
  head = next;
}
 return pre;
}
void reverse1(pnode head,int count)//把链表的节点值放在数组中,倒置数组
{
 int a[5]= {0};
 
 for(int i=0; i<count,head->pnext!=NULL; i++)
 {
  a[i]=head->pnext->data;
  head=head->pnext;
 
 }
 for(int j=0,i=count-1; j<count; j++,i--)
  printf("%d ",a[i]);
 
}
 
pnode reverse3(pnode pre,pnode cur,pnode t)//递归实现链表倒置
{
 
 cur -> pnext = pre;
 if(t == NULL)
  return cur; //返回无头节点的指针,遍历的时候注意
 reverse3(cur,t,t->pnext);
 
}
 
pnode new_reverse3(pnode head){ //新的递归转置
 
 if(head == NULL || head->next == NULL)
  return head;
 pnode new_node = new_reverse3(head->next);
 head->next->next = head;
 head->next = NULL;
 return new_node; //返回新链表头指针
 
}
int main()
{
 pnode p=CreateNode();
 pnode p3=CreateNode();
 int n=list(p);
 printf("1反转之后: ");
 reverse1(p,n);
 printf(" ");
 printf("2反转之后: ");
 pnode p1=reverse2(p);
 list(p1);
 p3 -> pnext = reverse3(NULL,p3 -> pnext,p3->pnext->pnext);
 printf("3反转之后: ");
 list(p3);
 free(p);
 free(p1);
 free(p3);
 return 0;
}

毫无疑问,递归是解决的最简单方法,四行就能解决倒置问题。

思路参考:http://www.zzvips.com/article/177887.html

这里注意: head ->next = pre; 以及 pre = head->next,前者把head->next 指向 pre,而后者是把head->next指向的节点赋值给pre。如果原来head->next 指向 pnext节点,前者则是head重新指向pre,与pnext节点断开,后者把pnext值赋值给pre,head与pnext并没有断开。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对服务器之家的支持。

原文链接:https://blog.csdn.net/sinat_36899414/article/details/75267365

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部