剑指Offer-24 实现链表反转 三个指针+递归(2020.7.26)

剑指offer24-实现链表反转

1. 三个指针翻转

思路：
(1)：设置3指针，pre，cur和next_node
(2)：实现局部反转，cur.next = pre
(3)：然后对指针进行跟新，让3个指针向前移动一位
(4)：特殊情况：当没有节点是要进行判断。当进行next_node更新时候也要进行判断，若cur = None 时 next_node = cur.next 则会报错。

class Node():

    def __init__(self, item):
        self.items = item # 存储当前节点数据
        self.next = None # 下一个节点信息(地址) 刚开始没有next

# 链表
class Link():

    def __init__(self):
        self._head = None # 初始化一个空链表 head用于记录第一个节点的地址


    def travel(self):
        # _head在链表创建好之后一定是不可边得
        cur = self._head
        while cur:
            print(cur.items)
            cur = cur.next


    def append(self, item):
        node = Node(item)

        # 特殊情况：链表为空则前面直接为0报错，在此判断
        if self._head == None:
            self._head = node
            return
        cur = self._head
        pre = None # 第一个节点之前肯定为None
        while cur:
            pre = cur # 这样我们就可以取到none之前的节点了
            cur = cur.next

        # 当cur.next=None时候 不能直接赋给新加入的节点即不能循环结束后cur.next=node应该是前一个
        pre.next = node


    def reverse(self):
        # 判断特殊情况，没有节点
        if self._head == None:
            return self._head
        cur = self._head
        pre = None
        next_node = cur.next

        while cur:
            cur.next = pre # 局部反转，然后p，c，n分别更新
            pre = cur
            cur = next_node
            if cur:  # 若cur更新为null那么就不要在更新next_node否则报错
                next_node = cur.next

        self._head = pre
        return self._head

link = Link()
link.append(1)
link.append(2)
link.append(3)
link.append(4)
link.append(5)

link.travel()

link.reverse()
link.travel()

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

2. 递归

    def reverseList(self, head):

        if not head:
            return None
        if not head.next:
            self._head = head
            return head

        headNode = self.reverseList(head.next)
        
        head.next.next = head
        head.next = None
        return headNode
1
2
3
4
5
6
7
8
9
10
11
12
13