LeetCode-143. Reorder List

发表于 分类于

问题描述

You are given the head of a singly linked-list. The list can be represented as:

1
L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

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

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example :

img

1
2
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000

解答

这个问题分三步解决：

  1. 将链表从中间分为两个链表
  2. 反转后半部分链表
  3. 将反转后的链表与前半部分合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 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.
 */
const reorderList = function (head) {
  if (head === null || head.next === null) {
    return head
  }
  let pre = null
  let slow = head
  let fast = head
  while (fast !== null && fast.next !== null) {
    pre = slow
    slow = slow.next
    fast = fast.next.next
  }
  pre.next = null
  slow = reverseList (slow)
  return merge(head, slow)
}

function reverseList (head) {
  let pre = null
  let cur = head
  while (cur !== null) {
    let temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  return pre
}

function merge (head1, head2) {
  let p1 = head1
  let p2 = head2
  while (p1 !== null) {
    let temp1 = p1.next
    let temp2 = p2.next
    p1.next = p2
    // 如果p1是最后一个节点，应在p1后插入p2时终止循环
    if (temp1 === null) {
      break
    }
    p2.next = temp1
    p1 = temp1
    p2 = temp2
  }
  return head1
}