143. Reorder List.md

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.

/**
 * 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) {
        if(head==null || head.next==null){
            return;
        }
        ListNode prev=null,slow=head,fast=head,l1=head;
        while(fast!=null && fast.next!=null){
            prev=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        prev.next=null;
        ListNode l2=reverse(slow);
        merge(l1,l2);
    }        
    private void merge(ListNode l1,ListNode l2){
        while(l1!=null){
            ListNode n1=l1.next,n2=l2.next;
            l1.next=l2;
            if(n1==null) break;
            l2.next=n1;
            l1=n1;
            l2=n2;
        }
    }
    private ListNode reverse(ListNode head){
        ListNode prev=null,curr=head,next=null;
        while(curr!=null){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        return prev;
    }
}

/**
 * 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 curr=head;
        while(curr!=null && curr.next!=null){
            ListNode temp=curr;
            ListNode prevTemp=curr;
            while(temp.next!=null){
                prevTemp=temp;
                temp=temp.next;
            }
            prevTemp.next=temp.next;
            temp.next=curr.next;
            curr.next=temp;
            if(curr.next!=null) curr=curr.next.next;
        }
    }
}