143. 重排链表

题目描述

输入单链表的头节点 head，链表依次为 L0, L1, ..., Ln。

把它重排成 L0, Ln, L1, Ln-1, L2, Ln-2, ...，即从两端轮流取节点：先取开头一个，再取结尾一个，如此交替。

必须通过调整节点之间的连接来完成，不能只改节点里存的值。就地修改，函数不返回值。链表用数组表示。

示例 1

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

解释：依次取 1、4、2、3。

示例 2

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

解释：依次取 1、5、2、4，最后是中间的 3。

数据范围

链表长度在 [1, 5 * 10^4] 之间。
1 <= node.val <= 1000

解题思路：找中点+反转+合并

结果是“前半段”和“倒过来的后半段”交替穿插。分三步：① 快慢指针找中点，slow 停在前半段末尾；② 从 slow.next 断开，把后半段原地反转；③ 用 first、second 两个指针交替合并，每次先暂存两边的下一个节点，再把 second 插到 first 后面。

为什么正确

合并阶段：head 到 first 之前已经是重排好的前缀；first 开头是前半段剩下的部分，second 开头是反转后半段剩下的部分，后者长度等于前者或比前者少 1。

复杂度分析

时间 O(n)：找中点、反转、合并各扫一遍。空间 O(1)，只调整指针。

易错点

一定要把前半段末尾 slow.next 置为 None，否则合并后最后一个节点仍指向后半段，形成环。另外合并时要先保存 first.next 和 second.next，再改指针，否则会丢掉后面的节点。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def reorderList(self, head):
        if not head or not head.next:
            return
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        prev, cur = None, slow.next
        slow.next = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        first, second = head, prev
        while second:
            n1, n2 = first.next, second.next
            first.next = second
            second.next = n1
            first, second = n1, n2

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null, cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode n1 = first.next, n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1; second = n2;
        }
    }
}

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next)
            return;
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *prev = nullptr, *cur = slow->next;
        slow->next = nullptr;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode *first = head, *second = prev;
        while (second) {
            ListNode *n1 = first->next, *n2 = second->next;
            first->next = second;
            second->next = n1;
            first = n1; second = n2;
        }
    }
};

func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	var prev *ListNode; cur := slow.Next
	slow.Next = nil
	for cur != nil {
		nxt := cur.Next
		cur.Next = prev
		prev = cur
		cur = nxt
	}
	first, second := head, prev
	for second != nil {
		n1, n2 := first.Next, second.Next
		first.Next = second
		second.Next = n1
		first, second = n1, n2
	}
}

var reorderList = function(head) {
    if (!head || !head.next)
        return;
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let prev = null, cur = slow.next;
    slow.next = null;
    while (cur) {
        const nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    let first = head, second = prev;
    while (second) {
        const n1 = first.next, n2 = second.next;
        first.next = second;
        second.next = n1;
        first = n1; second = n2;
    }
};

function reorderList(head: ListNode | null): void {
    if (!head || !head.next)
        return;
    let slow: ListNode = head, fast: ListNode = head;
    while (fast.next && fast.next.next) {
        slow = slow.next!;
        fast = fast.next.next;
    }
    let prev: ListNode | null = null, cur: ListNode | null = slow.next;
    slow.next = null;
    while (cur) {
        const nxt: ListNode | null = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    let first: ListNode | null = head, second: ListNode | null = prev;
    while (second) {
        const n1: ListNode | null = first!.next, n2: ListNode | null = second.next;
        first!.next = second;
        second.next = n1;
        first = n1; second = n2;
    }
};

载入编辑器，自己跑一遍 →

其他解法

数组法用 O(n) 空间换来直观的双指针；主解法组合三个链表基本操作，只用 O(1) 空间。

解法 2：数组存节点时间 O(n)，空间 O(n)

先把链表节点按顺序存入数组，利用下标随机访问。用左右双指针 i、j，依次让 nodes[i] 指向 nodes[j]，再让 nodes[j] 指向 nodes[i+1]。两指针相遇后，把最后一个节点的 next 置空。

不需要反转和合并链表，写法简单。需要 O(n) 额外空间存放节点引用。

class Solution:
    def reorderList(self, head):
        if not head:
            return
        nodes = []
        while head:
            nodes.append(head)
            head = head.next
        i, j = 0, len(nodes) - 1
        while i < j:
            nodes[i].next = nodes[j]
            i += 1
            if i == j:
                break
            nodes[j].next = nodes[i]
            j -= 1
        nodes[i].next = None

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) nodes.add(cur);
        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i == j) break;
            nodes.get(j).next = nodes.get(i);
            j--;
        }
        nodes.get(i).next = null;
    }
}

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return;
        vector<ListNode*> nodes;
        for (ListNode* cur = head; cur; cur = cur->next) nodes.push_back(cur);
        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes[i]->next = nodes[j];
            i++;
            if (i == j) break;
            nodes[j]->next = nodes[i];
            j--;
        }
        nodes[i]->next = nullptr;
    }
};

func reorderList(head *ListNode) {
	if head == nil {
		return
	}
	nodes := []*ListNode{}
	for cur := head; cur != nil; cur = cur.Next {
		nodes = append(nodes, cur)
	}
	i, j := 0, len(nodes)-1
	for i < j {
		nodes[i].Next = nodes[j]
		i++
		if i == j {
			break
		}
		nodes[j].Next = nodes[i]
		j--
	}
	nodes[i].Next = nil
}

var reorderList = function(head) {
    if (!head) return;
    const nodes = [];
    for (let cur = head; cur; cur = cur.next) nodes.push(cur);
    let i = 0, j = nodes.length - 1;
    while (i < j) {
        nodes[i].next = nodes[j];
        i++;
        if (i === j) break;
        nodes[j].next = nodes[i];
        j--;
    }
    nodes[i].next = null;
};

function reorderList(head: ListNode | null): void {
    if (!head) return;
    const nodes: ListNode[] = [];
    for (let cur: ListNode | null = head; cur; cur = cur.next) nodes.push(cur);
    let i = 0, j = nodes.length - 1;
    while (i < j) {
        nodes[i].next = nodes[j];
        i++;
        if (i === j) break;
        nodes[j].next = nodes[i];
        j--;
    }
    nodes[i].next = null;
}

链表专题的其他题目

查看链表全部题目 →