数据结构与算法——第2章-单链表的反转(2.3.2)

发表于 分类于 ， ， 阅读时长 ≈ 2 分钟

一 概述

1
2
3
4
5
1.什么是链表反转
2.迭代反转链表
3.递归
4.头插法
5.就地逆置法

二 什么是链表反转

反转前 反转后

经过反转（翻转、逆置）后，得到如下新链表

三 迭代反转链表

3.1 原理

1
从当前链表的首元节点开始，一直遍历至链表的最后一个节点，期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点

3.2 原理演示

2.1 实现方法：定义 3 个指针并分别命名为 beg、mid、end，初始指向如下

2.2 移动一个节点

1
2
3
4
5
6
7
在上图的基础上，遍历链表的过程就等价为：
3 个指针每次各向后移动一个节点，直至 mid 指向链表中最后一个节点（此时 end 为 NULL ）。

注意：这 3 个指针在移动之前都需要做一步操作，即改变 mid 所指节点的指针域，另其指向和 beg 相同。

在上图的基础上，先改变 mid 所指节点的指针域指向，
另其和 beg 相同（即改为 NULL），然后再将 3 个指针整体各向后移动一个节点：

2.3 再移动一个节点

1
2
在上图基础上，先改变 mid 所指节点的指针域指向，另其和 beg 相同（指向节点 1 ），
再将 3 个指针整体各向后移动一个节点

2.4 继续移动

1
2
在上图基础上，先改变 mid 所指节点的指针域指向，令其和 beg 相同（指向节点 2 ），
再将 3 个指针整体各向后移动一个节点

2.5 反转节点

1
2
上图中，虽然 mid 指向了原链表最后一个节点，但显然整个反转的操作还差一步，
即需要最后修改一次 mid 所指节点的指针域指向，另其和 beg 相同（指向节点 3）

3.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
注意：这里只需改变 mid 所指节点的指向即可，不用修改 3 个指针的指向。
最后只需改变 head 头指针的指向，另其和 mid 同向，就实现了链表的反转

// 迭代反转法, head 为无头节点链表的头指针
link * iteration_reverse(link* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    else {
        link * beg = NULL;
        link * mid = head;
        link * end = head->next;
        // 一直遍历
        while (1)
        {
            // 修改 mid 所指节点的指向
            mid->next = beg;
            // 此时判断 end 是否为 NULL, 如果成立则退出循环
            if (end == NULL) {
                break;
            }
            // 整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        // 最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

四 递归

4.1 原理

1
2
3
4
递归反转法更适用于反转不带头节点的链表。

和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，
依次向前遍历，遍历过程依次改变各节点的指向，另其指向前一个节点。

4.2 原理演示

第1步 第2步 第3步 第4步

4.3 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
link* recursive_reverse(link* head) {
    // 递归的出口; 空链或只有一个结点, 直接返回头指针
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    else
    {
        // 一直递归, 找到链表中最后一个节点
        link *new_head = recursive_reverse(head->next);
        // 当逐层退出时, new_head 的指向都不变, 一直指向原链表
        // 中最后一个节点递归每退出一层, 函数中 head 指针的指向
        // 都会发生改变, 都指向上一个节点每退出一层, 都需要改变
        // head->next 节点指针域的指向, 同时令 head 所指节点
        // 的指针域为 NULL
        head->next->next = head;
        head->next = NULL;
        // 每一层递归结束, 都要将新的头指针返回给上一层; 由此, 即
        // 可保证整个递归过程中, 能够一直找得到新链表的表头;
        return new_head;
    }
}

五 头插法

5.1 原理

1
2
在原有链表的基础上，依次将位于链表头部的节点摘下，
然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

5.2 原理演示

第1步 第2步 第3步 第4步

5.3 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
link * head_reverse(link * head) {
    link * new_head = NULL;
    link * temp = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL)
    {
        temp = head;
        // 将 temp 从 head 中摘除
        head = head->next;
        // 将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

六 就地逆置法

6.1 原理

1
2
3
4
就地逆置法和头插法的实现思想类似，唯一的区别：
头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。

在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 beg 和 end）

6.2 原理演示

第1步 第2步 第3步 第4步

6.3 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
link * local_reverse(link * head) {
    link * beg = NULL;
    link * end = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    beg = head;
    end = head->next;
    while (end != NULL) {
        // 将 end 从链表中摘除
        beg->next = end->next;
        // 将 end 移动至链表头
        end->next = head;
        head = end;
        // 调整 end 的指向, 另其指向 beg 后的一个节点, 为反转
        // 下一个节点做准备
        end = beg->next;
    }
    return head;
}

七 参考

  • CSDN—单链表的反转（4 种方法）