Sunday, September 14, 2014

Reverse Linked List

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example: Given 1->2->3->4->5->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note: Given mn satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
Label the m-th node(label) and the node before m-th node (prelabel). Insert nodes afterwards till the n-th node one by one between prelabel and label. 

prelabel: 1
label: 2
1 -> 3 -> 2 -> 4 -> 5
1 -> 4 -> 3 -> 2 -> 5

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null)
            return null;
        if (m == n)
            return head;
            
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int index = 1;
        ListNode prelabel = dummy;
        for (index = 1; index < m; index++)
        {
            prelabel = head;
            head = head.next;
            if (head == null)
                return null;
        }
        ListNode prev = head;
        ListNode label = head;
        head = head.next;
        //index ++;
        for (index = m + 1; index <= n; index++)
        {
            label.next = head.next;
            prelabel.next = head;
            head.next = prev;
            prev = head;
            head = label.next;
        }
        return dummy.next;
    }
}

No comments:

Post a Comment