Leetcode 92 Solution

This article provides solution to leetcode question 92 (reverse-linked-list-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 92" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/reverse-linked-list-ii

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) {
        ListNode* m_prev = NULL;
        ListNode* p = head;
        ListNode* prev = NULL;
        ListNode* newhead = head;



        for (int i = 1; i < m; i++)
        {
            if (m_prev == NULL)
            {
                m_prev = head;
                p = head->next;
                prev = NULL;
            }
            else
            {
                m_prev = m_prev->next;
                p = m_prev->next;
                prev = m_prev;
            }
        }



        for (int i = 0; i < n - m + 1; i++)
        {
            ListNode* next = p->next;



            if (i != 0)
            {
                prev->next = p->next;



                if (m_prev)
                {
                    p->next = m_prev->next;
                    m_prev->next = p;
                }
                else
                {
                    p->next = newhead;
                    newhead = p;
                }
            }



            if (i == 0)
                prev = p;
            p = next;
        }



        if (m_prev == NULL)
            return newhead;
        else
            return head;
    }
};