Reverse Linked List Ii - Leetcode Solution

Problem Statement:

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:

To solve this problem, we need to first traverse the linked list and reach the node (m-1)th position from where we need to start the reversal. We need to keep a track of the (m-1)th node so that we can connect it to the reversed part of the linked list.

After getting to the (m-1)th node, we can start reversing the linked list from the mth node to the nth node. To do this, we need to keep track of three pointers:

• prev: It will point to the (m-1)th node from where the reversal will start.
• curr: It will point to the mth node which will be the last node of the reversed part.
• next: It will point to the (n+1)th node which will be the first node of the remaining part of the linked list.

We will iterate through the linked list from the mth node to the nth node and keep reversing the pointers until we reach the nth node. After the reversal is done, we will connect the (m-1)th node to the nth node. Also, we will connect the mth node to the (n+1)th node.

At last, we will return the head of the linked list.

Code:

ListNode* reverseBetween(ListNode* head, int m, int n) { if(!head || !head->next || m==n) return head;

ListNode *dummy = new ListNode(-1);
dummy->next = head;

ListNode *prev = dummy;
for(int i=1; i<m; i++)
    prev = prev->next;

ListNode *curr = prev->next;
ListNode *next = curr->next;

for(int i=m; i<n; i++) {
    ListNode *temp = next->next;
    next->next = curr;
    curr = next;
    next = temp;
}

prev->next->next = next;
prev->next = curr;

return dummy->next;

}

Explanation:

• We have declared a new ListNode named dummy of value -1 which is pointing to the head of the linked list.
• We need to move the pointer prev to (m-1)th position after which we need to start the reversal.
• Next, we create the curr pointer and start the reversal from the mth node.
• We create the next pointer and keep iterating through the linked list from mth to nth node to reverse the pointers.
• After the reversal is done, we connect the (m-1)th node to the nth node and the mth node to the (n+1)th node.
• At last, we return the head of the modified linked list without the dummy node. The node at position 0(i.e -1) which acts as an imaginary head.

Time Complexity: O(N) Space Complexity: O(1)

1