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结点的前一个），将三者按顺序连起来即可。

class Solution:
    def rotateRight(self, head, k):
        if head is None:
            return None
        length = 1
        p = head
        while p.next:
            p = p.next
            length += 1
        if k == length:
            return head
        elif k > length:
            k = k % length
        cn = 1
        q = head
        while cn < (length - k):
            q = q.next
            cn += 1
        p.next = head
        newhead = q.next
        q.next = None
        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 的插入到分割点左侧（这一步实现可能比较费劲）。

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

class Solution:
    def partition(self, head, x):
        if head is None:
            return head
        p1 = ListNode(-1)
        p2 = ListNode(-1)
        h1, h2 = p1, p2
        while head:
            if head.val < x:
                p1.next = head
                p1 = p1.next
            else:
                p2.next = head
                p2 = p2.next
            head = head.next
        p2.next = None
        p1.next = h2.next
        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

题目解析

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

代码如下：

class Solution:
    def reverseBetween(self, head, m, n):
        if head is None:
            return head
        elif m == n:
            return head
        new = ListNode(-1)
        new.next = head
        head = new

        p = head
        pre = head
        for i in range(m):
            pre = p
            p = p.next
        q = p
        for i in range(n - m):
            q = q.next

        pre_p = q.next
        cur = p
        for i in range(n - m + 1):
            h = cur
            tmp = cur.next
            cur.next = pre_p
            pre_p = cur
            cur = tmp
        pre.next = q
        return head.next

注意的地方

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