simple iterative solution


  • 0
    K

    public void reorderList(ListNode head) {

        if(head==null||head.next==null||head.next.next==null)
            return;
        //find the middle element and divide the list in two halves
        ListNode slow=head,fast=head.next;
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast!=null)
                fast = fast.next;
        }
        ListNode secondHead = slow.next;
        slow.next = null;
        
        //reverse second list
        ListNode prev=null,curr=secondHead,temp=curr.next;
        while(curr!=null){
            curr.next = prev;
            prev = curr;
            curr = temp;
            if(temp!=null) temp = temp.next;
        }
        secondHead = prev;
        
        //merge the lists
        ListNode temp1=head,temp2=secondHead,curr2=temp2.next,curr1=temp1.next;
        while(temp1!=null&&temp2!=null){
            temp2.next = temp1.next;
            temp1.next = temp2;
            temp1 = curr1;
            temp2 = curr2;
            if(curr2!=null)
                curr2 = curr2.next;
            curr1 = curr1.next;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.