48 lines
942 B
JavaScript
48 lines
942 B
JavaScript
/**
|
|
* 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) {
|
|
let slow = head
|
|
let fast = head
|
|
|
|
// 使用快慢指针寻找链表中点
|
|
while (fast.next && fast.next.next) {
|
|
fast = fast.next.next
|
|
slow = slow.next
|
|
}
|
|
|
|
// 拆分成前后链表
|
|
let cur = slow.next
|
|
slow.next = null
|
|
|
|
// 反转后链表
|
|
let pre = null
|
|
while (cur) {
|
|
let next = cur.next // 4 null
|
|
cur.next = pre // null 3
|
|
pre = cur // 3 4
|
|
cur = next // 4 null
|
|
// null <- 3 <- 4
|
|
}
|
|
|
|
// 合并前后链表
|
|
let lp = head
|
|
while (lp && pre) {
|
|
let ln = lp.next
|
|
let rn = pre.next
|
|
lp.next = pre
|
|
pre.next = ln
|
|
lp = ln
|
|
pre = rn
|
|
}
|
|
|
|
return head
|
|
}; |