Friday, November 2, 2012

Reverse a linked list from position m to n (in-place and in one-pass)

Problem: Reverse a linked list from position m to n. Do it in-place and in one-pass.

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL) {
            return NULL;
        }
        ListNode *iter = head;
        int i;
    
        for (i = 1; i < m-1; i++)
            iter = iter->next;
        // Now iter points to (m-1)th node if m > 1.
       
        ListNode* cur, *curNext, *prev, *startReversing;
       
        // cur node at which we start reversing the link list.
        // prev node refer to node before cur.
        // Storing the first node, where linklist started reversing
        if (m == 1) {
            cur = iter;
            prev = NULL;
        } else {
            cur = iter->next;
            prev = iter;
        }
        startReversing = cur;
       
        // Reversing the linklist.    
        for (i = n-m; i > 0; i--) {
            curNext = cur->next;
            cur->next = prev;
            prev = cur;
            cur = curNext;
        }
        if ( m != n) {
            // Now curNext point to (n+1)th node.
            curNext = cur->next;
            cur->next = prev;
            // Set the next of mth node (starting node of linklist reversal) to (n+1)th node.
            startReversing->next = curNext;
        }
        if (m == 1) {
            // Return nth node.
            return cur;
        } else {
            // Set the next of (m-1)th node to reverse linklist head.
            iter->next = cur;
        }
        return head;
    }
};

============ Another Solution ==================


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *first = head, *store_first = NULL, *next = head, *prev = NULL, *prev_join = NULL;

        int count = n - m;
       
        while (m > 1) {
            prev_join = first;
            first = first->next;
            m--;
        }

        while ( count >= 0) {
            next = first->next;
            first->next = prev;
            if (prev == NULL) {
                store_first = first;
            }
            prev = first;
            first = next;

            count--;
        }

        store_first->next = first;
       
        if (prev_join != NULL) {
            prev_join->next = prev;
        } else {
            return prev;
        }
        return head;
    }
};

No comments:

Post a Comment