[LeetCode] 143. Reorder List

重排链表。题意很简单，

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

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

时间O(n)

空间O(1)

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;
};

Java实现

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode temp = null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode l1 = head;
        while (fast != null && fast.next != null) {
            temp = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        temp.next = null;
        ListNode l2 = reverse(slow);
        merge(l1, l2);
    }

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

    private void merge(ListNode l1, ListNode l2) {
        while (l1 != l2) {
            ListNode n1 = l1.next;
            ListNode n2 = l2.next;
            l1.next = l2;
            if (n1 == null)
                break;
            l2.next = n1;
            l1 = n1;
            l2 = n2;
        }
    }
}

另一种Java实现，把getMiddle写成一个函数，注意while循环的部分

/**
 * 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;
        }
    }
}

LeetCode 题目总结