经典的反转链表三种解决思路。

问题

问题：实现一个函数，输入一个链表的头结点，反转该链表并输出反转后的链表的头结点。

先实现单链表版本，然后实现双链表版本。

滑动指针

原理：

反转链表的其实就是在链表上调整指针的方向，而整体上的反转需要局部上的反转。只要实现了局部上的反转，将局部反转应用与整个链表就能得到反转的链表。局部的反转如下：我们先对链表上的结点依据顺序三三组合。

例如现在有四个结点的链表：

1
Node<1>->Node<2>->Node<3>->Node<4>

三三组合就有两种：

1
2
Node<1>->Node<2>->Node<3>
Node<2>->Node<3>->Node<4>

定义三个指针：

  • p_node
  • p_prev
  • p_reversed_head

为了避免出现断链，我们在翻转p_node和p_prev时需要先保存p_node.next。

实现：

先实现链表。方便生产测试用例，编写build_linked_list函数，通过输入序列建立链表，输出该链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def __repr__(self):
        return "Node<{}>".format(self.value)

def build_linked_list(node_list):
    if not node_list:
        return Node(None)
    root = Node(node_list[0])
    val = root # 当做游标使用
    for value in node_list[1:]:
        node = Node(value)
        val.next = node
        val = node
    return root

def travel_list(p_node):
    while p_node:
        print(p_node)
        p_node = p_node.next

反转链表的函数的实现，遍历方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def reverse_list(root):
    if root is None or root.next is None:
        return root

    p_reversed_head = None
    p_node = root
    p_prev = None
    while p_node:
        # 防止断链，保存后一根指针
        p_next = p_node.next
        # 判断p_node是否最为最后结点
        if p_next is None:
            p_reversed_head = p_node
        # 翻转指针
        p_node.next = p_prev
        # 指针向后移动以为
        p_prev = p_node
        p_node = p_next
    return p_reversed_head

测试，先建立Node<1>->Node<2>->···->Node<9>链表

1
2
3
4
5
6
7
8
root = build_linked_list(list(range(1, 10)))
print("travel list:")
travel_list(root)

reverse_root = reverse_list(root)

print("travel reverse list")
travel_list(reverse_root)

输出结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
travel list:
Node<1>
Node<2>
Node<3>
Node<4>
Node<5>
Node<6>
Node<7>
Node<8>
Node<9>
travel reverse list
Node<9>
Node<8>
Node<7>
Node<6>
Node<5>
Node<4>
Node<3>
Node<2>
Node<1>

这正是我们所期待的结果。

详细代码如下，包括了清晰的注释

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
class Node:

    def __init__(self, value):
        self.value = value
        self.next = None

def reversed_list(head):
    # 关于边界条件
    if head is None:
        return head
    # 其实下面的操作可以兼容这部分
    # 但卸载这里可以更快中断函数
    if head.next is None:
        return head

    p_prev = None
    p_node = head
    p_reversed_head = None

    while p_node != None:
        # 在翻转前保存下一节点，防止翻转时出现断链
        p_next = p_node.next
        if p_next is None:
            # 判断p_node是否为最后结点，如果是
            # 它就是翻转后链表的头结点
            p_reversed_head = p_node

        # 翻转p_prev和p_node
        p_node.next = p_prev
        # p_prev p_node 向后移动一个结点
        p_prev = p_node
        p_node = p_next

    return p_reversed_head

def test():
    values = list(range(1, 11))
    print(values)

    head = Node(0)
    p_node = head
    for v in values:
        p_node.next = Node(v)
        p_node = p_node.next

    head = head.next
    reversed_list_head = reversed_list(head)
    p_node = reversed_list_head
    while p_node:
        print(p_node.value, end=' ')
        p_node = p_node.next

if __name__ == '__main__':
    test()

借助辅助空间

另外还有一种思路，借助Stack辅助空间，从头到尾遍历链表依次保存结点到栈中，然后依次弹出栈的中元素，由于栈的FILO特性，弹出的序列为链表的尾到链表的头。实现如下：

首先需要一个栈结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Stack:
    def __init__(self):
        self._s = []

    def push(self, item):
        self._s.append(item)

    def pop(self):
        return self._s.pop()

    def empty(self):
        return len(self._s) == 0

    def top(self):
        if self.empty():
            return None
        return self._s[-1]

实现遍历链表的函数

1
2
3
4
def travel_yield_list(p_node):
    while p_node:
        yield p_node
        p_node = p_node.next

实现反转链表函数。有一个细节需要处理：反转后的链表的最后一个结点需要指向None，因为这个结点是没有反转时的头结点，它指向第二个结点。而反转后的第二个结点又指向反转链表后的最后一个结点，于是出现了环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def reverse_list_with_stack(root):
    if root is None:
        return
    stack = Stack()
    for node in travel_yield_list(root):
        stack.push(node)

    root = stack.pop()
    p_node = root
    while not stack.empty():
        node = stack.pop()
        p_node.next = node
        p_node = node
    p_node.next = None # 最后一个结点要指向None
    return root

测试代码如下

1
2
3
4
5
6
7
8
root = build_linked_list(list(range(1, 10)))
print("travel list:")
travel_list(root)

reverse_root = reverse_list_with_stack(root)

print("travel reverse list")
travel_list(reverse_root)

栈操作可以看作是递归操作的直观版本，根据栈操作的方法，可以把反转链表改为递归操作方法。最后，我们使用一种递归思路来解决反转链表问题。

递归方法

具体思路：
假设现在有三个结点的链表：Node<1>—>Node<2>—>Node<3>。为了反转链表，我们需要先反转结点1、2间的链，但如果反转了，结点2的指针就不是指向Node<3>了，于是出现断链，除非结点2和结点三间的链已经反转了。为了解决断链问题，我们先把反转Node<1>和Node<2>间的链的操作压人栈（执行递归调用，该递归调用的操作就是把Node<2>和Node<3>间的链反转）。待递归调用返回后才把Node<1>和Node<2>间的链反转。这就是递归反转链表的核心，剩下的就是边界处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def _reversed(p_head):
    p_node = p_head
    if p_head.next is None:
        return p_node, p_head
    node, p_head = _reversed(p_node.next)
    node.next = p_node
    return p_node, p_head

def reverse_list_recursively(p_head):
    if p_head is None:
        return 
    p_node, p_head = _reversed(p_head)
    p_node.next = None
    return p_head

总结

上述采用了三种思路：

  • 通过指针操作
  • 通过栈作辅助空间
  • 使用递归

第二种思路采用了栈作辅助空间，编写实现更直观，但需要对尾结点做处理，否则会出现环。第一种思路采用三指针，有一定的操作技巧。第三种思路和第二种思路本质是相同的，只是在实现上，思路二更具体也更容易理解，第三种思路把栈的操作过程隐藏在递归过程中。

以上实现源码可参考github