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 class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null) return ; ListNode fast = head; ListNode slow = head; while(fast.next!=null){//worng here, has to check even odd time condition fast = fast.next; if(fast.next!=null){//check fast.next.next != null or not fast = fast.next; //protect if fast.next.next is null } else{ break; } slow = slow.next; } ListNode head1 = head, head2 = slow.next;//split up list by two parts slow.next = null;// wrong detach the two sublists //reverse second half ListNode cur = head2; ListNode post = cur.next; cur.next = null; //make first node next to null while(post!=null){ // post -> cur ->next ListNode temp = post.next; post.next = cur; cur = post; post = temp; } head2 = cur; // new head of revesed list ListNode p = head1; ListNode q = head2; while( q!=null){//check second half of list not to be null is enough! ListNode temp1 = p.next; ListNode temp2 = q.next; p.next = q; q.next = temp1; p = temp1;//move to original next q = temp2; } } }
mistakes: 1)bounty problem 2) when have fast and slow pointers , check fast.next first then do fast.next.next
learned: 1) reverse linked list set first one to be null 2)merge two lists make a1->b1->a2 then move to next