143. Reorder List

[Tcdian]

143. Reorder List

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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.

[Tcdian]

Solution

• JavaScript Solution

/**
 * 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) {
    const reversedPart = reverseList(findMidPoint(head));
    mergeList(head, reversedPart);

    function findMidPoint(head) {
        let patrol = new ListNode(-1);
        patrol.next = head;
        let slow = patrol;
        let fast = patrol;
        while (fast !== null && fast.next !== null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (slow !== null) {
            const part = slow.next;
            slow.next = null;
            return part;
        }
        return null;
    }
    function reverseList(head) {
        let prev = null;
        while(head !== null) {
            let temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    function mergeList(l1, l2) {
        let patrol = new ListNode(-1);
        while (l1 !== null && l2 !== null) {
            patrol.next = l1;
            l1 = l1.next;
            patrol = patrol.next;
            patrol.next = l2;
            l2 = l2.next;
            patrol = patrol.next;
        }
        patrol.next = l1 || l2;
    }
};

• TypeScript Solution

/**
 * 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 reversedPart = reverseList(findMidPoint(head));
    mergeList(head, reversedPart);

    function findMidPoint(head: ListNode | null): ListNode | null {
        let patrol = new ListNode(-1);
        patrol.next = head;
        let slow: ListNode | null = patrol;
        let fast: ListNode | null = patrol;
        while (fast !== null && fast.next !== null) {
            fast = fast.next.next;
            slow = (slow as ListNode).next;
        }
        if (slow !== null) {
            const part = slow.next;
            slow.next = null;
            return part;
        }
        return null;
    }
    function reverseList(head: ListNode | null): ListNode | null {
        let prev: ListNode | null = null;
        while(head !== null) {
            let temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    function mergeList(l1: ListNode | null, l2: ListNode | null) {
        let patrol: ListNode | null = new ListNode(-1);
        while (l1 !== null && l2 !== null) {
            patrol.next = l1;
            l1 = l1.next;
            patrol = patrol.next;
            patrol.next = l2;
            l2 = l2.next;
            patrol = patrol.next;
        }
        patrol.next = l1 || l2;
    }
};