Back to Linked List
Medium
Reorder List
You are given the head of a singly linked-list. The list can be represented as: `L0 → L1 → … → Ln-1 → Ln`. Reorder the list to be on the following form: `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.
Examples
Input:head = [1,2,3,4]
Output:[1,4,2,3]
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 * 10^4].1 <= Node.val <= 1000
Approach
Traverse the linked list and store all nodes in an array. Once all nodes are in the array, use two pointers (`left` at the beginning and `right` at the end) to reconstruct the linked list by alternating between the `left` and `right` pointers.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This uses O(n) auxiliary space to store the node references.
Solution.java
class Solution { public void reorderList(ListNode head) { if (head == null) return; List<ListNode> nodes = new ArrayList<>(); ListNode curr = head; while (curr != null) { nodes.add(curr); curr = curr.next; } int i = 0; int j = nodes.size() - 1; while (i < j) { nodes.get(i).next = nodes.get(j); i++; if (i == j) break; nodes.get(j).next = nodes.get(i); j--; } nodes.get(i).next = null; }}