Monday, May 26, 2014

Reverse Linked List II

For this problem, the basic idea is to move the mth node in the linked list right behind the nth node, i.e. "8". One thing to notice is that every time one node is moved, we always pick the node after the (m-1) th node, and move it behind that node "8". Since node "8" should be moved forward, it is wrong to keep moving the mth node behind nth node, which should be not node "8" any more.

In my solution, variable preNNode might be unnecessary. The following code can be improved later.
/**
 * Definition for singly-linked list.
 * 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|| m > n || m <= 0 || n <= 0) return null;
        if (m == n) return head;
        int preMIdx = m - 1;
        int preNIdx = n - 1;
     
        ListNode preMNode = head;
        ListNode preNNode = head;
        ListNode mNode = head;      
        ListNode nNode = head;

        if(preMIdx == 0){// In this case, m is 1
            nNode = preNNode.next;
            int i = 1;
            while(i < n - 1 && preNNode != null && nNode != null){
                preNNode = preNNode.next;
                nNode = nNode.next;
                i++;
            }
            if(preNNode == null || nNode == null){
                return null;
            }
            // ListNode insertAfterNode = nNode;
            while(head != nNode){// move the mth element behind nth, untill the next one of m-1th node is that nth one
                mNode = head.next;
                // preMNode.next = mNode.next;
                head.next = nNode.next;
                nNode.next = head;
                head = mNode;
                // insertAfterNode = insertAfterNode.next;
            }          
        }
        else{
            mNode = preMNode.next;
            int i = 1;
            while(i < m - 1 && preMNode != null && mNode != null){
                preMNode = preMNode.next;
                mNode = mNode.next;
                i ++;
            }
            if(preMNode == null || mNode == null){
                return null;
            }          
            nNode = preNNode.next;
            i = 1;
            while(i < n - 1 && preNNode != null && nNode != null){
                preNNode = preNNode.next;
                nNode = nNode.next;
                i ++;
            }
            if(preNNode == null || nNode == null){
                return null;
            }
            // ListNode insertAfterNode = nNode;
            while(preMNode.next != nNode){// move the mth element behind nth, untill the next one of m-1th node is that nth one
             
                preMNode.next = mNode.next;
                mNode.next = nNode.next;
                nNode.next = mNode;
                mNode = preMNode.next;
                // preMNode = preMNode.next;
                // insertAfterNode = insertAfterNode.next;
            }
        }
 
        return head;
    }
}

No comments:

Post a Comment