Open Zheaoli opened 1 year ago
/*
* @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
微信id: 弘树 来自 vscode 插件
2022-10-12