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 middleListNode p1=head;ListNode p2=head;while(p2.next!=null&&p2.next.next!=null){ p1=p1.next;p2=p2.next.next;}//reverse right halfListNode 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->4p1 = 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;}}
?
 PTS DTS)
)
)
