LeetCode 143. Reorder List

143. Reorder List

Difficulty: Medium

Given a singly linked list L: L0→L1→…→L__n-1→Ln,
reorder it to: L0→L__n_→L1→_L__n-1→L2→L__n-2→…

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

Example 1:

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

Example 2:

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

Solution

Language: Java

T(n) O(n)

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