143. Reorder List
Tags: ‘Linked List’
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:
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
- Reverse it by storying list in Stack.
- O(n) time O(n) space
- 38% 100%
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode p = head; // pointer
Deque<ListNode> stack = new ArrayDeque<>();
while(p != null) {
stack.push(p);
p = p.next;
}
p = stack.pop();
// start traverse using head and p (head and tail)
// connect head -> p -> head.next
// End Condition: two pointer meet(odd) or head.next == p(even)
while (head != p && head.next != p) {
ListNode temp = head.next;
head.next = p;
p.next = temp;
//increment head and p
head = temp;
p = stack.pop();
}
if (head == p){
head.next = null;
} else if (head.next == p) {
p.next = null;
}
}
}
- Reverse second half
- O(n) time O(1) space
- Make sure extra node belong to left half, if # is odd
- check even/odd: if left != null in the end , it means odd
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// find middle
ListNode slow = head, fast = head, pre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) {// when # is odd, incremend 1 step to make sure extra node belong to left half
pre = slow;
slow = slow.next;
}
pre.next = null;
// Reverse second half
ListNode prev = null;
while (slow != null) {
ListNode next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
} // prev should be the tail (start of second half)
ListNode p1 = head, p2 = prev;
while(p1 != null && p2 != null) {
ListNode temp = p2.next;
p2.next = p1.next;
p1.next = p2;
p1 = p1.next.next;
p2 = temp;
}
}
}