Question

143. 重排链表

English Version

题目描述

给定一个单链表 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]

 

提示：

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

解法

方法一：快慢指针 + 反转链表 + 合并链表

我们先用快慢指针找到链表的中点，然后将链表的后半部分反转，最后将左右两个链表合并。

时间复杂度 $O(n)$，其中 $n$ 是链表的长度。空间复杂度 $O(1)$。

# 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:
    # 快慢指针找到链表中点
    fast = slow = head
    while fast.next and fast.next.next:
      slow = slow.next
      fast = fast.next.next

    # cur 指向右半部分链表
    cur = slow.next
    slow.next = None

    # 反转右半部分链表
    pre = None
    while cur:
      t = cur.next
      cur.next = pre
      pre, cur = cur, t
    cur = head

    # 此时 cur, pre 分别指向链表左右两半的第一个节点
    # 合并
    while pre:
      t = pre.next
      pre.next = cur.next
      cur.next = pre
      cur, pre = pre.next, t

/**
 * 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) {
    // 快慢指针找到链表中点
    ListNode fast = head, slow = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }

    // cur 指向右半部分链表
    ListNode cur = slow.next;
    slow.next = null;

    // 反转右半部分链表
    ListNode pre = null;
    while (cur != null) {
      ListNode t = cur.next;
      cur.next = pre;
      pre = cur;
      cur = t;
    }
    cur = head;

    // 此时 cur, pre 分别指向链表左右两半的第一个节点
    // 合并
    while (pre != null) {
      ListNode t = pre.next;
      pre.next = cur.next;
      cur.next = pre;
      cur = pre.next;
      pre = t;
    }
  }
}

/**
 * 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) {
    // 快慢指针找到链表中点
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast->next && fast->next->next) {
      slow = slow->next;
      fast = fast->next->next;
    }

    // cur 指向右半部分链表
    ListNode* cur = slow->next;
    slow->next = nullptr;

    // 反转右半部分链表
    ListNode* pre = nullptr;
    while (cur) {
      ListNode* t = cur->next;
      cur->next = pre;
      pre = cur;
      cur = t;
    }
    cur = head;

    // 此时 cur, pre 分别指向链表左右两半的第一个节点
    // 合并
    while (pre) {
      ListNode* t = pre->next;
      pre->next = cur->next;
      cur->next = pre;
      cur = pre->next;
      pre = t;
    }
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func reorderList(head *ListNode) {
  // 快慢指针找到链表中点
  fast, slow := head, head
  for fast.Next != nil && fast.Next.Next != nil {
    slow, fast = slow.Next, fast.Next.Next
  }

  // cur 指向右半部分链表
  cur := slow.Next
  slow.Next = nil

  // 反转右半部分链表
  var pre *ListNode
  for cur != nil {
    t := cur.Next
    cur.Next = pre
    pre, cur = cur, t
  }
  cur = head

  // 此时 cur, pre 分别指向链表左右两半的第一个节点
  // 合并
  for pre != nil {
    t := pre.Next
    pre.Next = cur.Next
    cur.Next = pre
    cur, pre = pre.Next, t
  }
}

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

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
  const arr = [];
  let node = head;
  while (node.next != null) {
    arr.push(node);
    node = node.next;
  }
  let l = 0;
  let r = arr.length - 1;
  while (l < r) {
    const start = arr[l];
    const end = arr[r];
    [end.next.next, start.next, end.next] = [start.next, end.next, null];
    l++;
    r--;
  }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//   ListNode {
//     next: None,
//     val
//   }
//   }
// }
use std::collections::VecDeque;
impl Solution {
  pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
    let mut tail = &mut head.as_mut().unwrap().next;
    let mut head = tail.take();
    let mut deque = VecDeque::new();
    while head.is_some() {
      let next = head.as_mut().unwrap().next.take();
      deque.push_back(head);
      head = next;
    }
    let mut flag = false;
    while !deque.is_empty() {
      *tail = if flag { deque.pop_front().unwrap() } else { deque.pop_back().unwrap() };
      tail = &mut tail.as_mut().unwrap().next;
      flag = !flag;
    }
  }
}

/**
 * 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) {
  // 快慢指针找到链表中点
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // cur 指向右半部分链表
  let cur = slow.next;
  slow.next = null;

  // 反转右半部分链表
  let pre = null;
  while (cur) {
    const t = cur.next;
    cur.next = pre;
    pre = cur;
    cur = t;
  }
  cur = head;

  // 此时 cur, pre 分别指向链表左右两半的第一个节点
  // 合并
  while (pre) {
    const t = pre.next;
    pre.next = cur.next;
    cur.next = pre;
    cur = pre.next;
    pre = t;
  }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   public int val;
 *   public ListNode next;
 *   public ListNode(int val=0, ListNode next=null) {
 *     this.val = val;
 *     this.next = next;
 *   }
 * }
 */
public class Solution {
  public void ReorderList(ListNode head) {
    // 快慢指针找到链表中点
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }

    // cur 指向右半部分链表
    ListNode cur = slow.next;
    slow.next = null;

    // 反转右半部分链表
    ListNode pre = null;
    while (cur != null) {
      ListNode t = cur.next;
      cur.next = pre;
      pre = cur;
      cur = t;
    }
    cur = head;

    // 此时 cur, pre 分别指向链表左右两半的第一个节点
    // 合并
    while (pre != null) {
      ListNode t = pre.next;
      pre.next = cur.next;
      cur.next = pre;
      cur = pre.next;
      pre = t;
    }
  }
}

方法二

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

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
  let slow = head;
  let fast = head;
  // 找到中心节点
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // 反转节点
  let next = slow.next;
  slow.next = null;
  while (next != null) {
    [next.next, slow, next] = [slow, next, next.next];
  }
  // 合并
  let left = head;
  let right = slow;
  while (right.next != null) {
    const next = left.next;
    left.next = right;
    right = right.next;
    left.next.next = next;
    left = left.next.next;
  }
}