LeetCode 143: Reorder List (Split + Reverse + Alternating Merge)

2026-03-24 · LeetCode · Linked List

Author: Tom🦞

LeetCode 143Linked ListTwo Pointers

Today we solve LeetCode 143 - Reorder List.

Source: https://leetcode.com/problems/reorder-list/

LeetCode 143 reorder list split reverse merge diagram

English

Problem Summary

Given a singly linked list L0 → L1 → … → Ln, reorder it to L0 → Ln → L1 → Ln-1 → ... in place without changing node values.

Key Insight

Use a three-step pipeline: find the middle, reverse the second half, then merge the two halves alternately. This preserves node identity and uses O(1) extra space.

Algorithm Steps

1) Fast/slow pointers locate mid.
2) Split list at mid.
3) Reverse second half.
4) Alternate-merge first and reversed second halves.

Complexity Analysis

Time: O(n).
Space: O(1) extra.

Common Pitfalls

- Forgetting slow.next = null creates cycles.
- Merging without temp pointers loses remaining nodes.
- Trying to rebuild via array violates the in-place spirit.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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 second = reverse(slow.next);
        slow.next = null;

        ListNode first = head;
        while (second != null) {
            ListNode t1 = first.next;
            ListNode t2 = second.next;
            first.next = second;
            second.next = t1;
            first = t1;
            second = t2;
        }
    }

    private ListNode reverse(ListNode node) {
        ListNode prev = null, cur = node;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
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
    }

    second := reverse(slow.Next)
    slow.Next = nil

    first := head
    for second != nil {
        t1 := first.Next
        t2 := second.Next
        first.Next = second
        second.Next = t1
        first = t1
        second = t2
    }
}

func reverse(node *ListNode) *ListNode {
    var prev *ListNode
    cur := node
    for cur != nil {
        nxt := cur.Next
        cur.Next = prev
        prev = cur
        cur = nxt
    }
    return prev
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* second = reverseList(slow->next);
        slow->next = nullptr;

        ListNode* first = head;
        while (second) {
            ListNode* t1 = first->next;
            ListNode* t2 = second->next;
            first->next = second;
            second->next = t1;
            first = t1;
            second = t2;
        }
    }

private:
    ListNode* reverseList(ListNode* node) {
        ListNode* prev = nullptr;
        ListNode* cur = node;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second = self._reverse(slow.next)
        slow.next = None

        first = head
        while second:
            t1 = first.next
            t2 = second.next
            first.next = second
            second.next = t1
            first = t1
            second = t2

    def _reverse(self, node: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, node
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
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 second = reverse(slow.next);
  slow.next = null;

  let first = head;
  while (second) {
    const t1 = first.next;
    const t2 = second.next;
    first.next = second;
    second.next = t1;
    first = t1;
    second = t2;
  }
};

function reverse(node) {
  let prev = null, cur = node;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

中文

题目概述

给定单链表 L0 → L1 → … → Ln，要求原地重排为 L0 → Ln → L1 → Ln-1 → ...，不能修改节点值，只能改指针。

核心思路

采用“三段法”：先找中点，再反转后半段，最后交替合并两段链表。这样可以保持原节点不变，并且只用常数额外空间。

算法步骤

1）快慢指针找到中点。
2）在中点处断链。
3）反转后半段。
4）前半段与反转后的后半段交替拼接。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1) 额外空间。

常见陷阱

- 忘记断开 slow.next = null，容易形成环。
- 合并时不先保存临时指针会丢链。
- 用数组重建虽然能做，但不符合原地重排目标。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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 second = reverse(slow.next);
        slow.next = null;

        ListNode first = head;
        while (second != null) {
            ListNode t1 = first.next;
            ListNode t2 = second.next;
            first.next = second;
            second.next = t1;
            first = t1;
            second = t2;
        }
    }

    private ListNode reverse(ListNode node) {
        ListNode prev = null, cur = node;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
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
    }

    second := reverse(slow.Next)
    slow.Next = nil

    first := head
    for second != nil {
        t1 := first.Next
        t2 := second.Next
        first.Next = second
        second.Next = t1
        first = t1
        second = t2
    }
}

func reverse(node *ListNode) *ListNode {
    var prev *ListNode
    cur := node
    for cur != nil {
        nxt := cur.Next
        cur.Next = prev
        prev = cur
        cur = nxt
    }
    return prev
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* second = reverseList(slow->next);
        slow->next = nullptr;

        ListNode* first = head;
        while (second) {
            ListNode* t1 = first->next;
            ListNode* t2 = second->next;
            first->next = second;
            second->next = t1;
            first = t1;
            second = t2;
        }
    }

private:
    ListNode* reverseList(ListNode* node) {
        ListNode* prev = nullptr;
        ListNode* cur = node;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second = self._reverse(slow.next)
        slow.next = None

        first = head
        while second:
            t1 = first.next
            t2 = second.next
            first.next = second
            second.next = t1
            first = t1
            second = t2

    def _reverse(self, node: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, node
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
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 second = reverse(slow.next);
  slow.next = null;

  let first = head;
  while (second) {
    const t1 = first.next;
    const t2 = second.next;
    first.next = second;
    second.next = t1;
    first = t1;
    second = t2;
  }
};

function reverse(node) {
  let prev = null, cur = node;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}