[LeetCode] 143. Reorder List

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 * 104].
1 <= Node.val <= 1000

重排链表。

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路也很直观，但是代码容易错，算是链表题里面的综合题吧，有链表的快慢指针fast-slow pointer，反转reverse，和merge两个链表三个技能点的考察。找快慢指针的时候记得设一个temp node，因为slow停下的地方会是second half的起点，这个temp指针会停在first half的尾部。

复杂度

时间O(n)
空间O(1)

代码

Java实现

/**
 * 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) {
        // corner case
        if (head == null || head.next == null) {
            return;
        }
        // normal case
        ListNode middle = findMiddle(head);
        ListNode first = head;
        ListNode second = middle.next;
        middle.next = null;
        second = reverse(second);
        merge(first, second);
    }

    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    private void merge(ListNode left, ListNode right) {
        ListNode leftTemp;
        ListNode rightTemp;
        while (left != null && right != null) {
            leftTemp = left.next;
            rightTemp = right.next;
            left.next = right;
            right.next = leftTemp;
            left = leftTemp;
            right = rightTemp;
        }
    }
}

JavaScript实现

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    if (!head || !head.next) return;
    let fast = head;
    let slow = head;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    let second = reverseList(slow.next);
    slow.next = null;
    let first = head;
    while (second) {
        let temp = second.next;
        second.next = first.next;
        first.next = second;
        first = first.next.next;
        second = temp;
    }
};

var reverseList = function(head) {
    let pre = null;
    while (head !== null) {
        let next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
};