143. 重排链表 Medium

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:
输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2:
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

解题思路

输入： 一个链表 head

输出： 对链表重新排列，要求收尾交替排列 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

本题属于链表重排类问题。

这道题可以分三个步骤来解决

1. 利用快慢指针找到链表的中点
2. 从中点开始反转链表的后半部分
3. 交错合并整个链表
   • 前半段：1 → 2 → 3
   • 后半段反转：6 → 5 → 4
   • 交错合并：1 → 6 → 2 → 5 → 3 → 4

代码实现

python

def middleNode(head):
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow

def reverseList(head):
    pre, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # 先求出中间节点
        mid = middleNode(head)
        # 再将中间节点后半部分反转得到尾节点并且一路指向中间节点
        # 1(head) -> 2 -> 3 <- 4 <- 5(head2)
        head2 = reverseList(mid)
        # 从 head2 开始循环直到找到 mid 节点，因为反转后 mid 节点指向 None
        while head2.next:
            # 1(head) -> 2 -> 3 -> 4 -> 5
            # 5(head2) -> 4 -> 3(mid)
            # 保存 head 下一个节点
            nxt = head.next
            # 保存 head2 下一个节点
            nxt2 = head2.next
            # 将 head 下一个节点指向 head2: 1 -> 5
            head.next = head2
            # 将 head2 下一个节点指向 head.next: 5 -> 2
            head2.next = nxt
            # 移动 head 到原本的下一个节点
            head = nxt
            # 移动 head2 到原本的下一个节点
            head2 = nxt2

        # 栈解法
        curr = head
        stack = []

        # 备份一份链表
        while curr:
            stack.append(curr)
            curr = curr.next
        
        curr = head
        while stack:
            nxt = curr.next
            # 不断从后往前取出节点
            stackNxt = stack.pop()

            # 相遇时有奇数偶数两种情况，此时需要退出
            # 1 -> 2(nxt | stackNxt)
            if nxt == stackNxt:
                nxt.next = None
                break

            # 1 -> 2(curr | stackNxt) -> 3(nxt)
            if curr == stackNxt:
                curr.next = None
                break
            # 否则就将当前节点下一个节点指向末尾节点: 1 -> 5
            curr.next = stackNxt
            # 末尾节点下一个节点指向 nxt: 5 -> 2
            stackNxt.next = nxt
            # 移动当前节点
            curr = nxt
        return head

javascript

var reorderList = function(head) {
    function middleNode(head) {
        let slow = head;
        let fast = head;

        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    function reverseList(head) {
        let pre = null;
        let curr = head;
        while (curr) {
            const nxt = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nxt;
        }

        return pre;
    }

    let mid = middleNode(head);
    let head2 = reverseList(mid);

    while (head2.next) {
        const nxt = head.next;
        const nxt2 = head2.next;

        head.next = head2;
        head2.next = nxt;
        head = nxt;
        head2 = nxt2;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

143 国际版

143 中文版