Sunday, September 21, 2014

Leetcode: Reverse Linked List II

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.
Understand the problem:
The problem asks for reversing a linked list from position m to n. Note that 1 <= m <= n <= length. The problem also requires for in-place and one-pass traversal of the linked list. 

Solution:
/**
 * 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 || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        head = dummyNode;
        
        ListNode prev = dummyNode;
        ListNode start = dummyNode.next;
        ListNode end = dummyNode.next;
        
        // move end pointer n - m steps ahead;
        for (int i = 0; i < n - m; i++) {
            end = end.next;
        }
        
        // move all the three pointers to m - 1 steps
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
            start = start.next;
            end = end.next;
        }
        
        ListNode nextNode = end.next;
        end.next = null;
        
        // Reverse linked list from start to end
        ListNode newHead = reverseList(start);
        
        prev.next = newHead;
                
        start.next = nextNode;
        
        return dummyNode.next;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr= head;
        
        while (curr != null) {
            ListNode nextNode = curr.next;
            
            curr.next = prev;
            prev = curr;
            
            curr = nextNode;
        }
        
        return prev;
    }
}

Update 10/8/14:
/**
 * 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 || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next  = head;
        
        int count = 1;
        /// Find the tail node of the first segment
        ListNode firstTail = dummyNode;
        while (count < m) {
            firstTail = firstTail.next;
            count++;
        }
        
        /// reverse the middle segement
        ListNode midTail = firstTail.next;
        ListNode midHead = firstTail.next;
        
        ListNode prev = null;
        int num = n - m + 1;
        int i = 0;
        while (i < num) {
            ListNode next = midHead.next;
            midHead.next = prev;
            prev = midHead;
            midHead = next;
            i++;
        }
        
        /// Link with the third segment
        firstTail.next = prev;
        midTail.next = midHead;
        
        return dummyNode.next;
        
    }
}


No comments:

Post a Comment