LeetCode 143. 重排链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：找中点 + 反转 + 合并（推荐）
相似题目

题目描述

✅ 143. 重排链表

题目：

给定单链表的头节点 head，链表中的节点按顺序 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]

提示：

链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000

思路分析

解法一：找中点 + 反转 + 合并（推荐）

核心思路：

将问题拆分为三步经典子问题：

找中点：快慢指针，fast 每次走两步，slow 每次走一步，slow 停在中间节点

反转后半段：从 slow.next 开始，原地反转后半链表，切断与前半的连接

交叉合并：前半段 l1 和反转后的后半段 l2 交替连接：l1 → l2 → l1.next → l2.next → ...

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(1)，仅使用常数个额外指针。

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 pre = null;
        ListNode cur = slow.next;
        // 切断前后两部分
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // 第三步：交叉合并前后两段
        ListNode l1 = head, l2 = pre;
        while (l2 != null) {
            ListNode next1 = l1.next, next2 = l2.next;
            l1.next = l2;
            l2.next = next1;
            l1 = next1;
            l2 = next2;
        }
    }
}

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 pre *ListNode
	cur := slow.Next
	// 切断前后两部分
	slow.Next = nil
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	// 第三步：合并两个链表
	l1, l2 := head, pre
	for l2 != nil {
		next1, next2 := l1.Next, l2.Next
		l1.Next = l2
		l2.Next = next1
		l1 = next1
		l2 = next2
	}
}

相似题目

题目	难度	考察点
2095. 删除链表的中间节点	中等	快慢指针
206. 反转链表	简单	链表反转基础
876. 链表的中间结点	简单	快慢指针找中间节点
234. 回文链表	简单	找中间+反转+比较
21. 合并两个有序链表	简单	链表合并
25. K 个一组翻转链表	困难	链表分段操作
148. 排序链表	中等	链表拆分+归并

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/43660029