Reverse Linked List II

Problem Statement

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.

Examples

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$

Algorithm

1. Create a dummy node pointing to the head of the list to handle edge cases easily.
2. Find the node just before the left position (leftNode) and the node at the left position (curr).
3. Reverse the sublist from left to right.
4. Reconnect the reversed sublist back to the list.
5. Return the new head of the list (dummy.next).

Pseudocode

function reverseLinkedList(head, left, right):
    if head is null:
        return null

    dummy = new ListNode(0)
    dummy.next = head
    leftNode = dummy
    curr = head

    for i from 0 to left-2:
        leftNode = leftNode.next
        curr = curr.next

    subhead = curr
    preNode = null

    for i from 0 to right-left:
        nextNode = curr.next
        curr.next = preNode
        preNode = curr
        curr = nextNode

    leftNode.next = preNode
    subhead.next = curr

    return dummy.next

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseLinkedList(self, head: ListNode, left: int, right: int) -> ListNode:
        if not head:
            return None

        dummy = ListNode(0)
        dummy.next = head
        leftNode = dummy
        curr = head

        for i in range(left - 1):
            leftNode = leftNode.next
            curr = curr.next

        subhead = curr
        preNode = None

        for i in range(right - left + 1):
            nextNode = curr.next
            curr.next = preNode
            preNode = curr
            curr = nextNode

        leftNode.next = preNode
        subhead.next = curr

        return dummy.next

Java

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseLinkedList(ListNode head, int left, int right) {
        if (head == null) return null;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode leftNode = dummy;
        ListNode curr = head;

        for (int i = 0; i < left - 1; i++) {
            leftNode = leftNode.next;
            curr = curr.next;
        }

        ListNode subhead = curr;
        ListNode preNode = null;

        for (int i = 0; i <= right - left; i++) {
            ListNode nextNode = curr.next;
            curr.next = preNode;
            preNode = curr;
            curr = nextNode;
        }

        leftNode.next = preNode;
        subhead.next = curr;

        return dummy.next;
    }
}

C++

class ListNode {
public:
    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* reverseLinkedList(ListNode* head, int left, int right) {
        if (!head) return nullptr;

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

        ListNode* leftNode = dummy;
        ListNode* curr = head;

        for (int i = 0; i < left - 1; i++) {
            leftNode = leftNode->next;
            curr = curr->next;
        }

        ListNode* subhead = curr;
        ListNode* preNode = nullptr;

        for (int i = 0; i <= right - left; i++) {
            ListNode* nextNode = curr->next;
            curr->next = preNode;
            preNode = curr;
            curr = nextNode;
        }

        leftNode->next = preNode;
        subhead->next = curr;

        return dummy->next;
    }
};

JavaScript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

var reverseLinkedList = function (head, left, right) {
  if (!head) return null;

  let dummy = new ListNode(0);
  dummy.next = head;
  let leftNode = dummy;
  let curr = head;

  for (let i = 0; i < left - 1; i++) {
    leftNode = leftNode.next;
    curr = curr.next;
  }

  let subhead = curr;
  let preNode = null;

  for (let i = 0; i <= right - left; i++) {
    let nextNode = curr.next;
    curr.next = preNode;
    preNode = curr;
    curr = nextNode;
  }

  leftNode.next = preNode;
  subhead.next = curr;

  return dummy.next;
};