14. Reverse Linked List II

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

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Solution:

Algorithm:

class Solution
{
public:
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {

        if (m == n)
        {
            return head;
        }

        int i = 1;
        ListNode *p = head;
        ListNode *q = NULL;

        while (i != m)
        {
            q = p;
            p = p->next;
            i++;
        }

        ListNode *cur = p;
        ListNode *prev = q;
        ListNode *temp = p;

        i = 0;
        while (i <= n - m)
        {
            temp = temp->next;

            cur->next = prev;
            prev = cur;
            cur = temp;

            i++;
        }
        if (q == NULL)
        {
            head = prev;
        }
        else
        {
            q->next = prev;
        }

        p->next = cur;
        return head;
    }
};

Time Complexity: O(n)