On this page

    ☰

    链表专题

    61 旋转链表

    给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

    143 重排链表

    142

    假设入口为 $A$， 到入口的距离为 $x$， 快慢指针相遇点为 $B$， $A$ 到 $B$ 的距离为 $y$， $B$ 到 $A$ 的距离为 $z$。

    那么当快慢指针相遇时， 两指针走过的距离为：

    \[l_1 = x + y + k_1(y + z)\] \[l_2 = x + y + k_2(y + z)\]

    又:

    \[x + y + k_2(y + z) = 2(x + y + k_1(y + z))\]

    有：

    \[x + y = (k_2 - 2k_1)(y + z) \Rightarrow x = (k_1 - 2k_1 -1)(y + z) + z\]

    也就是说 $x$ 的长度为环的周长的整数倍加上 BA 的长度。 如果两个指针分别从头和从 B 点开始走， 那么一个指针到达 A 点时， 另一个指针也必然到达。

    class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return None
        slow = fast = head
        while fast:
            slow = slow.next
            fast = fast.next
            if fast: fast = fast.next
            else: break

            if slow == fast:
                fast = head
                while(fast != slow):
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

    206 反转链表

    class Solution:
    """
        - c = b->next
        - b ->next = a
        - a = b, b = c
    """
    def reverseList(self, head: ListNode) -> ListNode:
        if not head: return None
        a = head
        b = head.next
        while b:
            c = b.next
            b.next = a
            a = b
            b = c
        head.next = None
        return a