143. Reorder List

143. Reorder Listopen in new window

🟠 🔖 栈 递归 链表 双指针 🔗 LeetCodeopen in new window

题目

You are given the head of a singly linked-list. The list can be represented as:

L0 -> L1 -> … -> Ln - 1 -> Ln

Reorder the list to be on the following form:

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

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10^4].
1 <= Node.val <= 1000

题目大意

按照指定规则重新排序链表：第一个元素和最后一个元素排列在一起，接着第二个元素和倒数第二个元素排在一起，接着第三个元素和倒数第三个元素排在一起。

解题思路

最近简单的方法是先把链表存储到数组里，然后找到链表中间的结点，按照规则拼接即可。这样时间复杂度是 O(n)，空间复杂度是 O(n)。

更好的做法是结合之前几道题的操作：链表逆序，找中间结点。

先找到链表的中间结点，然后利用逆序区间的操作，如第 92 题里的 reverseBetween() 操作，只不过这里的反转区间是从中点一直到末尾。最后利用 2 个指针，一个指向头结点，一个指向中间结点，开始拼接最终的结果。这种做法的时间复杂度是 O(n)，空间复杂度是 O(1)。

代码

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  if (!head || !head.next) return head;

  // 寻找中间节点
  let slow = head;
  let fast = head;
  while (fast && fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast?.next?.next;
  }

  // 反转后一半链表，eg: 1->2->3->4->5->6 to 1->2->3->6->5->4
  const middle = slow;
  let cur = middle.next;
  while (cur.next) {
    let temp = cur.next;
    cur.next = temp.next;
    temp.next = middle.next;
    middle.next = temp;
  }

  // 按要求重新拼接链表，eg: 1->2->3->6->5->4 to 1->6->2->5->3->4
  let p3 = head;
  let p4 = middle.next;
  while (p3 != middle) {
    middle.next = p4.next;
    p4.next = p3.next;
    p3.next = p4;
    p3 = p4.next;
    p4 = middle.next;
  }
};

143. Reorder List

# 143. Reorder Listopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

143. Reorder Listopen in new window

题目

题目大意

解题思路

代码

相关题目