2022-10-12

[github-actions]

No description provided.

[gongpeione]

143 Reorder List

/*
 * @lc app=leetcode id=143 lang=typescript
 *
 * [143] Reorder List
 */

// @lc code=start
/**
 * 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 {
    // find the middle of this list
    let slowPointer = head;
    let fastPointer = head.next;
    while(fastPointer && fastPointer.next) {
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }

    // this is the start of the second list
    let secondHead = slowPointer.next;

    // break down the list
    slowPointer.next = null;

    // reverse the second list
    let prev = null;
    while(secondHead) {
        const tmp = secondHead.next;
        secondHead.next = prev;
        prev = secondHead;
        secondHead = tmp;
    }

    // reorder the list
    let firstList = head;
    let secondList = prev;
    while (secondList) {
        const tmp1 = firstList.next;
        const tmp2 = secondList.next;

        firstList.next = secondList;
        secondList.next = tmp1;
        firstList = tmp1;
        secondList = tmp2;
    }
};
// @lc code=end

---

Nickname: Geeku
From vscode-hzfe-algorithms