LeetCode 143. Reorder List

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 1 分钟
LeetCode 143. Reorder List

143. Reorder List

Difficulty: Medium

Given a singly linked list L: _L_0→_L_1→…→L__n-1→_L_n,
reorder it to: _L_0→L__n→_L_1→L__n-1→_L_2→L__n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

1
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

1
2
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Solution

Language: Java

T(n) O(n)

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode start = slow.next;
        slow.next = null;
        while (start != null) {
            stack.push(start);
            start = start.next;
        }
        slow = head;
        while (!stack.isEmpty()) {
            ListNode n = stack.pop();
            n.next = slow.next;
            slow.next = n;
            slow = n.next;
        }
    }
}