[LeetCode] 143. Reorder List

Posted on | In

Problem

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Explanation

  1. Make a cur pointer to the head, while the pointer is not null, push cur pointer’s node to the stack.

  2. Note, if there are 4 nodes like 1->2->3->4, then we only need to pop n = (stack.size()-1)/2 = (4-1)/2 = 1 time. Because we just want to connect 1->4, but 2->3 is already connected. After we finish poping n times, we set 3->null, which is st.peek().next = null.

  3. Make cur pointer points back to the head. Now the top node of the stack is the next node of cur. We can pop it and set it to cur.next and move the cur to the right position and decrease the counter.

Solution

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
/**
 * 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;

        Stack<ListNode> st = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            st.push(cur);
            cur = cur.next;
        }

        cur = head;
        int n = (st.size()-1)/2;
        while (n-- > 0) {
            ListNode next = cur.next;
            ListNode popNode = st.pop();
            cur.next = popNode;
            popNode.next = next;
            cur = next;
        }
        st.peek().next = null;
    }
}