143. 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}.

public void ReorderList(ListNode head) {
        if(head == null|| head.next == null) return;
        //find middle
        ListNode p1=head;
        ListNode p2=head;
        while(p2.next!=null&&p2.next.next!=null){ 
                p1=p1.next;
                p2=p2.next.next;
        }
        
        //reverse right half
        ListNode standMiddle = p1;
        p1 = p1.next;
        ListNode newHead = null;
        ListNode nextNode =null;
        while(p1 != null)
        {
            nextNode = p1.next;
            p1.next = newHead;
            newHead = p1; 
            p1 = nextNode;
        }
        standMiddle.next = newHead;
        
        //Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
        p1 = head;
        p2 = standMiddle.next;
        while(p1 !=standMiddle)
        {
            nextNode = p2.next;
            standMiddle.next = nextNode;
            p2.next = p1.next;
            p1.next = p2;
            p1 = p2.next;
            p2 = nextNode;
        }
    }

相关推荐