Reorder List
Given a singly linked list
L: L0 → L1 → … → Ln-1 → Ln,
reorder it to:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
Method:
Reverse the second part of the linkedlist, and then combine them.
Solution:
Time: O(n)
Space: O(1)
/**
* Definition for singly-linked list.
* class ListNode {
* public int val;
* public ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
// s f
// s f
// 1->2->3->4 => 3
// s f
// s f
// 1->2->3->4->5 => 3
private ListNode findMid(ListNode A) {
ListNode slow = A;
ListNode fast = A;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 1->2->3->4
// 1<-2->3->4
private ListNode reverse(ListNode A) {
ListNode prev = null;
ListNode curr = A;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// 1->2->3
// 5->4->3
// 1->2->3
// 4->3
public ListNode reorderList(ListNode A) {
if (A == null || A.next == null) {
return A;
}
ListNode mid = findMid(A);
mid = reverse(mid);
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (A.next != null && mid != null) {
ListNode Anext = A.next;
p.next = A;
p = p.next;
p.next = mid;
p = p.next;
A = Anext;
mid = mid.next;
}
return dummy.next;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode mid = findMid(head);
ListNode a = head;
ListNode b = reverse(mid);
merge(a, b);
}
private void merge(ListNode a, ListNode b) {
// 1 -> 2 -> 3
// 5 -> 4
ListNode pA = a;
ListNode pB = b;
while (pA != null && pB != null) {
ListNode aNext = pA.next;
ListNode bNext = pB.next;
pA.next = pB;
pB.next = aNext;
pA = aNext;
pB = bNext;
}
}
private ListNode reverse(ListNode head) {
// 1 -> 2 -> 3 -> 4
// null <- 1 <- 2 -> 3 -> 4
ListNode p = head;
ListNode prev = null;
while (p != null) {
ListNode next = p.next;
p.next = prev;
prev = p;
p = next;
}
return prev;
}
private ListNode findMid(ListNode head) {
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
if (fast == null) {
ListNode ret = slow;
prev.next = null;
return ret;
}
if (fast.next == null) {
ListNode ret = slow.next;
slow.next = null;
return ret;
}
}
return head;
}
}