Reorder List
Source
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.
Example
For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.
Java
public class Solution {
public void reorderList(ListNode head) {
if(head==null || head.next==null) return;
ListNode slow=head;
ListNode fast=head;
ListNode pre=null;
while(fast!=null && fast.next!=null){
pre=slow;
slow=slow.next;
fast=fast.next.next;
}
while(slow!=null && slow.next!=null){
ListNode tmp = slow.next.next;
slow.next.next = pre.next;
pre.next = slow.next;
slow.next = tmp;
}
slow=head;
fast=pre.next;
pre.next=null;
while(slow!=pre){
ListNode tmp1= slow;
slow=slow.next;
tmp1.next=fast;
fast=fast.next;
tmp1.next.next=slow;
}
if(fast!=null){
slow.next=fast;
}
}
}