/*
* Problem:
Given a linked list 0 -> 1 -> 2 -> 3 -> ... -> n-2 -> n-1 -> n,
reorder the linked list as 0 -> n -> 1 -> n-1 -> 2 -> n-2 -> ...
Solution:
use fast-slow pointer to traversal the linked list.
when fast pointer find tail, the slow pointer is pointing to the middle point.
break the linked list to 2 sub-linked list at middle point.
reverse the second half
remove the node from second half
start from the head of first half, insert element behind each node
*/
public class ReorderLinkedList {
private static int SIZE = 10; //-10, 0, 1, 2, 3, 10, 11
private class LNode{
int value;
LNode next;
LNode(int value, LNode next) {
this.value = value;
this.next = next;
}
}
private void printLinkedList(LNode head) {
LNode current = head;
while(current != null) {
System.out.print(current.value + "->");
current = current.next;
}
System.out.println();
}
private LNode makeLinkedList() {
LNode head = new LNode(-10, null);
LNode current = head;
for(int i = 0; i <= SIZE; i++) {
current.next = new LNode(i, null);
current = current.next;
}
return head;
}
//6->7->8->9->10
private void reverseLinkedList(LNode head) {
if(head == null || head.next == null) return;
LNode pre = head;
LNode current = pre.next;
LNode next = current;
while(current != null) {
next = current.next;
current.next = pre;
pre = current;
current = next;
}
}
public static void main(String[] args) {
ReorderLinkedList rl = new ReorderLinkedList();
LNode head = rl.makeLinkedList();
rl.printLinkedList(head.next);
if(head == null || head.next == null || head.next.next == null) {
System.out.println("nothing to do");
return;
}
//find middle point and tail
LNode fast = head.next;
LNode slow = head.next;
//1->2->3->4->5->6->7->8->9->10
// , .
//1->2->3->4->5->6->7->8->9->10->11
// , .
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//terminate the first half at the middle point, adjust tail
LNode tail2 = (fast.next==null) ? fast : fast.next;
LNode head2 = slow.next;
slow.next = null;
//reverse the second half, tail2 pointer is *, head2 pointer is `
//before 7`->8->9->10->11*
rl.reverseLinkedList(head2);
//after 11*->10->9->8->7`
head2.next = null;
//traversal first half, insert elements from second half
LNode current1 = head.next;
LNode current2 = tail2;
LNode next1 = current1;
LNode next2 = current2;
while(!(current1 == null || current2 == null)) {
next1 = current1.next; //1->2*->3->4
current1.next = current2; //1->11
next2 = current2.next;
current2.next = next1; //1->11->2*->3->4
current1 = next1;
current2 = next2;
}
rl.printLinkedList(head.next);
}
}
