单向链表的反转

单向链表的反转

对单向链表的反转是非常经典的算法题,链表不同于数组,节点的遍历需要每个节点逐个访问下去。理解反转的过程能对线性表的链式存储结构有个充分的认识。为了方便理解(也为了防止自己日后忘了)所以尽可能仔细的记录其过程。

建表

首先定义链表结构:

1
2
3
4
5
6
typedef struct Node
{
int date;
struct Node * next;
} Node;
typedef Node * LinkList;

创建一个链表

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
//n 描述了数据数组长度
//尾插法
LinkList creatListTail(LinkList L,int a[], int n){
LinkList p,r;
L = (LinkList)malloc(sizeof(Node));
r = L;
for (int i = 0 ; i < n ;i++){
p = (LinkList)malloc(sizeof(Node));
p -> date = a[i];
r -> next = p;
r = p;
}
r ->next = NULL;
return L;
}
//头插法
LinkList creatListHead(LinkList L,int a[] ,int n){
LinkList p;
L = (LinkList)malloc(sizeof(Node));
L -> next = NULL;
for (int i = 0; i < n; i++){
p = (LinkList)malloc(sizeof(Node));
p ->date = a[i];
p -> next = L ->next;
L->next = p;
}
return L;
}

一定要注意自己的建表方法,因为尾插法插入是按照数据顺序建表的,而头插法则是逆序。如果你没注意到而用头插法顺序插入数据然后反转当然又变成了顺序了。为了演示这边使用的是尾插法。同时补上头插法的代码,因为头插法的思想在这里非常重要

我们以一个长度为5数组来演示:

1
a[5] = {1,2,3,4,5};

我们得到了一个以L为头指针,包含了五个节点的单向链表

反转

迭代法

把这条链表想象成一个字符串,如果让你逆序一个字符串”Hello World”,你会怎么做?除了对半交换外,还有个方法是创建一个新的空间然后逆序存放原字符串的每个字符。

我们也是这样,首先创建一个新的头节点 ,就叫它 NewL。让他的后继节点为NULL,是不是有点像头插法建表步骤, 同时新建一个p指针指向L表的第一个节点,也就是p = L -> next

现在我们可以让 p -> next指向 NewL?

指完就爆炸,不同于头插法那时我们一直在生成新的p节点,现在如果直接让 p 的下一节点指向新的表尾,那我们就丢失了L表中 p -> next,也就是p后继节点的位置,我们就没法遍历接下来的L表了,所以我们需要创建一个temp 来暂时存放p的后继节点,等到 p 也就是当前节点添加到新表完成后再让p回到temp继续。

  1. 我们先创建一个节点指针temp,让temp=p->next存储p的后继节点信息
  2. 接着我们就可以放心地让p指向新表的表尾(表尾是因为此时NewL还只是NULL)
1
2
temp = p -> next;	//让temp存放p后驱节点
p - > next = NewL -> next; //让p指向当前新表的后继

我们完成了一个节点的插入到新表,接下来我们要准备后续节点。首先我们让 NewL -> next = p 从而使接下来的节点始终插入在新表头指针后面,如果你了解头插法你就会发现这一过程极其相似,为了实现逆序我们就是以原来的L表用头插法来创建一个新表,头插法本身就是逆置建表,让p回到temp后进入下次循环,新节点会不断的插入在表头后,直到L表结束。

1
2
3
4
5
//头插法部分:
...
p -> next = L ->next; //头插入中我们让新节点的后继指向头节点的后继
L->next = p //然后让头节点的后继变成新节点从而在中间不断插入
...
1
2
3
4
5
//迭代法部分:
...
p ->next = NewL -> next;
NewL -> next = p;
...
  1. NewL 头指针后继指向p(新插入节点)
  2. p移动到temp位置回来原表,准备下次循环直到NULL

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkList  reverse(LinkList L){
if (L == NULL || L -> next == NULL){
return L;
}
LinkList p = L -> next;
LinkList NewL = (LinkList)malloc(sizeof(Node));
NewL -> next = NULL;
LinkList temp;
while(p != NULL){
temp = p->next;
p ->next = NewL -> next;
NewL -> next = p;
p = temp;
}
return NewL;
}

显示链表,注意这里链表都是有头节点

1
2
3
4
5
6
7
8
9
10
void display(LinkList L){
LinkList p;
//指向第一个节点
p = L -> next;
while (p != NULL)
{
printf("%d\n",p->date);
p = p -> next;
}
}

基本上就是迭代法实现单链表反转的过程。

后面会再讲讲还有一种方法递归法

Asahi
2019.10.16

Author

Asahi

Posted on

2019-10-16

Updated on

2022-09-23

Licensed under