Leetcode Study Day 28

Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:


Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]
 

Constraints:

The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Solution

The solution is first to find the node before the left node. Then we reverse the nodes from the left node to the right node. The solution in Leetcode explain how the reverse work step by step, which is very clear and clever.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0);
        // created dummy node
        dummy -> next = head;
        // intialising prev pointer on dummy node
        ListNode* prev = dummy;
        
        // set prev to the node that left to the node "Left"
        for (int i = 1; i < left; i++){
            prev = prev->next;
        }
        // current pointer will be just after prev
        ListNode* current = prev -> next;
        for (int i = 0; i < right-left; i++){
            // forw pointer will be after curr
            ListNode* forward = current -> next;
            current -> next = forward -> next;
            forward -> next = prev -> next;
            prev -> next = forward;
        }
        return dummy->next;
    }
};