反转链表

难度：简单

牛客-1

思路

反转链表主要调节原有链表的head.next指向，先定义一个pre = None，然后再定义一个cur指向当前head，定义一个next代表cur节点的下一个节点，然后必须按顺序执行下面四个步骤：

  1. 先让当前节点cur的下一个节点指向next，防止cur节点指向反转后找不到下一个节点，从而出现断链的情况；
  2. 将cur节点指向新创造的pre节点实现反转，一开始设置pre为空，反转后pre不再为空，而是代表当前节点cur的上一个节点，最终要返回的也是pre
  3. 让pre节点指向cur节点，实现pre节点的前移
  4. 让cur节点指向next节点

一直循环上面四个步骤，最后面cur指向None，pre指向最后一个节点，也就是反转后的头结点，实现链表反转；

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
class ListNode():
    def __init__(self, val):
        self.val = val
        self.next = None


class Solution():
    # ====================================================== 核心函数部分 ==========================================
    def Reverse(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

    def print_list(self, head: ListNode):
        cur = head
        while cur:
            print(str(cur.val) + '->', end=' ')
            cur = cur.next
    # ====================================================== 核心函数部分 ==========================================


if __name__ == '__main__':
    list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    head = ListNode(list[0])
    tail = head
    for node in list[1:]:
        tail.next = ListNode(node)
        tail = tail.next
    solution = Solution()
    solution.print_list(head)
    print('\n\n')
    pre = solution.Reverse(head)
    solution.print_list(pre)

链表内指定区间反转

牛客-2

思路

在头节点head前再定义一个哑巴节点dummy用来占位，先实例化这个哑巴节点dummy = ListNode(0)，然后将dummy.next指向头节点，最后返回dummy.next确保链表一定是从头节点开始的！思路如下：

  • 找到需要反转的子链表的起点的前一个节点pre_node，以及反转部分的第一个节点post_node。

  • 对子链表中的节点进行迭代，逐个将节点反转，子链表的第一个节点为start_node，最后一个节点为end_node。

  • 将反转后的子链表重新连接到主链表上，主链的头和反转后子链的头相连，主链的post_node和反转后子链的尾相连。

  • 返回新的链表头，dummy.next下一个指向head，所以返回哑巴节点的下一个节点(head)。

注意事项

end_node.next = None 这一步非常关键，它明确了需要反转的边界，使得 reverse 方法能够只处理想要反转的那一部分，确保了算法的正确性。如果没有 end_node.next = None 这一步，那么在调用 reverse 方法时，反转的将不仅仅是 m 到 n 之间的子链表，而是从 m 开始到链表末尾的所有节点。因为在 reverse 方法中，迭代会一直进行直到 cur 为 None，而cur是从start_node开始一直往链表末尾递增的，end_node指向的是子链的尾部，跟start_node在同一条链上，所以end_node断开链表cur就能知道什么时候停止了。

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
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @param m int整型
# @param n int整型
# @return ListNode类
#
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        dummy = ListNode(0)
        dummy.next = head

        pre_node = dummy
        for _ in range(m - 1):
            pre_node = pre_node.next

        start_node = pre_node.next
        end_node = start_node
        for _ in range(n - m):
            end_node = end_node.next

        post_node = end_node.next
        end_node.next = None

        def reverse(head: ListNode):
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre

        reverse_head = reverse(start_node)
        pre_node.next = reverse_head
        start_node.next = post_node
        return dummy.next