Sunday, March 5, 2017

Reorder Singly LInkedList

Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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) {
       
      ListNode slow, fast;
      slow=head;
      fast=head;
      // find middle of linked list
      while(slow != null && fast != null && fast.next !=null) {
          slow = slow.next;
          fast = fast.next.next;
      }
   
     // reverse second half of list and divide into two list
      ListNode secondHead = null;
      if(slow != null) {
        secondHead = reverse(slow.next);
        slow.next = null;
      }
     
     // join two lists with reoder
      slow = head;
      while(secondHead != null) {
          ListNode temp = slow.next;
          slow.next = secondHead;
          ListNode temp2 = secondHead.next;
          secondHead.next = temp;
          slow = temp;
          secondHead = temp2;
      }    
    }
   
    private ListNode reverse(ListNode L) {      
        ListNode prev = null;
        ListNode cur = L;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

No comments:

Post a Comment