Python 数据结构之链表 —— （三）链表右移、链表分割、链表逆序

zltzlt

来源于 CSDN

Python 数据结构之链表 —— （三）链表右移、链表分割、链表逆序

都是一些 LeetCode 上关于链表的题目，多刷一些这样的题目有助于我们全面熟悉链表那一套理论方法。

题目 1

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例：

输入：1->2->3->4->5->NULL, k = 2
输出：4->5->1->2->3->NULL
解释：
向右旋转 1 步：5->1->2->3->4->NULL
向右旋转 2 步：4->5->1->2->3->NULL

题目解析

找倒数第 k 个结点类似，先获取长度最关键，要注意对 k>=长度 的处理。

关键点在于利用三个结点：head（链表头），p（链表尾），q（倒数第k结点的前一个），将三者按顺序连起来即可。

1. class Solution:
   
2.     def rotateRight(self, head, k):
   
3.         if head is None:
   
4.             return None
   
5.         length = 1
   
6.         p = head
   
7.         while p.next:
   
8.             p = p.next
   
9.             length += 1
   
10.         if k == length:
    
11.             return head
    
12.         elif k > length:
    
13.             k = k % length
    
14.         cn = 1
    
15.         q = head
    
16.         while cn < (length - k):
    
17.             q = q.next
    
18.             cn += 1
    
19.         p.next = head
    
20.         newhead = q.next
    
21.         q.next = None
    
22.         return newhead

复制代码

题目 2

86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

题目解析

很难想到这题正确的解题思路，开始想象着找到分割的位置，然后将分割点两侧不应在这一组的结点 "交换"。

错就错在交换了，首先，链表的结点交换是操作中最复杂的操作，详细的可见鄙人所做的 py 的链表实现；

其次，交换破坏了原始相对位置。

这一思路可以改良为，将分割点左侧大于等于 x 的结点插入到分割点右侧（依次），将右侧小于 x 的插入到分割点左侧（这一步实现可能比较费劲）。

于是看了他人的思路，代码如下：

1. class Solution:
   
2.     def partition(self, head, x):
   
3.         if head is None:
   
4.             return head
   
5.         p1 = ListNode(-1)
   
6.         p2 = ListNode(-1)
   
7.         h1, h2 = p1, p2
   
8.         while head:
   
9.             if head.val < x:
   
10.                 p1.next = head
    
11.                 p1 = p1.next
    
12.             else:
    
13.                 p2.next = head
    
14.                 p2 = p2.next
    
15.             head = head.next
    
16.         p2.next = None
    
17.         p1.next = h2.next
    
18.         return h1.next

复制代码

申请两个头指针，只遍历一遍链表，将两类结点各自挑出来依次连接，最后再合并，实在是简洁高效！

时间复杂度 O(n)，空间复杂度 O(1) 。还是要领会这一思想。

思考

这一问题实际上说明，快速排序对于单链表存储结构仍然适用，所给的 x 其实是快排中的主元。

题目 3

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

示例：

输入：1->2->3->4->5->NULL, m = 2, n = 4
输出：1->4->3->2->5->NULL

题目解析

这是链表逆转操作的加强版，在基本功的逆序操作的基础上，将逆转后的链表头尾再连接到应该连接的地方。

代码如下：

1. class Solution:
   
2.     def reverseBetween(self, head, m, n):
   
3.         if head is None:
   
4.             return head
   
5.         elif m == n:
   
6.             return head
   
7.         new = ListNode(-1)
   
8.         new.next = head
   
9.         head = new
   
10. 
    
11.         p = head
    
12.         pre = head
    
13.         for i in range(m):
    
14.             pre = p
    
15.             p = p.next
    
16.         q = p
    
17.         for i in range(n - m):
    
18.             q = q.next
    
19. 
    
20.         pre_p = q.next
    
21.         cur = p
    
22.         for i in range(n - m + 1):
    
23.             h = cur
    
24.             tmp = cur.next
    
25.             cur.next = pre_p
    
26.             pre_p = cur
    
27.             cur = tmp
    
28.         pre.next = q
    
29.         return head.next

复制代码

注意的地方

• 当 m=1 时比较麻烦，所以一般涉及到链表头的改变的问题，可以在头部之前建一结点，这样可将问题一般化处理
• 特殊情况还有 m=n 时；
• 注意这几个结点的作用，pre 是 m 点之前的点，p（cur) 是 m 点，q 是 n 点，pre_p 即 q.next 是 m-n 逆转后尾部需要连接的地方（在其他的逆转问题中一般用 None）