143. Reorder List

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */

题目给我们一个链表头 head，要求我们把链表在原地从

L0 → L1 → … → Ln - 1 → Ln

重新构建为

 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

解题思路

我们观察新的链表结构，发现他们是一头一尾～一头一尾～直到最后

所以我们除了需要能从头按顺序拿元素，也需要能从尾巴反过来按顺序拿元素

所以这题的破局思路就是：我们需要反转后半链表

分成两步：

1. 用快慢指针找到中间元素
2. 以中间元素的下一个元素为新头，断开中间元素与新头的指针，然后反转新头的链表

最后，我们获得两个链表，链表头分别用 front 与 rear 表示（front 指向原来的 head；rear 指向原来的末尾元素）

接下来，我们就正常修改链表指针即可

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) {
    if(!head) {
        return head
    }
    // 1. find the middle node
    let slow = head
    let fast = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }

    // 2. reverse the rear part of the list
    let left = null
    let mid = slow.next
    slow.next = null
    while(mid) {
        let right = mid.next
        mid.next = left
        left = mid
        mid = right
    }

    // 3. modify the link list
    let front = head
    let rear = left
    while(rear) {
        let t1 = front.next
        let t2 = rear.next
        front.next = rear
        rear.next = t1
        front = t1
        rear = t2
    }
};

复杂度分析

n 为链表元素个数

时间

O(n)

空间

O(1)