Description:
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]Solution in Python:
To solve the problem of reversing a segment of a singly linked list between given positions left and right, you can follow these steps:
- Identify the part of the list to be reversed: Traverse the list to the node just before the
leftposition. - Reverse the sublist: Reverse the nodes between the
leftandrightpositions. - Reconnect the reversed sublist with the rest of the list: Ensure that the reversed sublist is correctly connected to the preceding and following parts of the list.
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
# Edge case: if the list is empty or left == right, no need to reverse
if not head or left == right:
return head
# Create a dummy node to simplify edge cases
dummy = ListNode(0)
dummy.next = head
# Initialize pointers
prev = dummy
current = head
# Step 1: Move the prev pointer to the node just before the 'left' position
for _ in range(left - 1):
prev = current
current = current.next
# Save the pointers to reconnect the reversed sublist
last_unswapped_node = prev
first_node_of_sublist = current
# Step 2: Reverse the sublist from 'left' to 'right'
prev = None
for _ in range(right - left + 1):
next_temp = current.next
current.next = prev
prev = current
current = next_temp
# Step 3: Reconnect the reversed sublist with the rest of the list
last_unswapped_node.next = prev
first_node_of_sublist.next = current
return dummy.nextDetailed Comments on the Code:
- Edge case handling:
- If the list is empty or
left == right, no action is needed as the list remains the same.
- If the list is empty or
- Using a dummy node:
- A dummy node is used to simplify the edge case where the head of the list is part of the reversal. This way, you can uniformly handle the list without checking if you are at the head of the list.
- Moving the
prevpointer:- Traverse the list until the node just before the
leftposition. This node is calledlast_unswapped_node.
- Traverse the list until the node just before the
- Reversing the sublist:
- Reverse the nodes between
leftandrightby changing thenextpointers of the nodes.
- Reverse the nodes between
- Reconnecting the list:
- After reversing, reconnect the
last_unswapped_nodeto the new head of the reversed sublist, and the end of the reversed sublist (first_node_of_sublist) to the node following therightposition.
- After reversing, reconnect the
By following these steps, you can reverse the specified portion of the list in a single pass, achieving the desired result efficiently.
Solution in Javascript:
JavaScript
// Definition for singly-linked list.
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
// Edge case: if the list is empty or left == right, no need to reverse
if (!head || left === right) {
return head;
}
// Create a dummy node to simplify edge cases
let dummy = new ListNode(0);
dummy.next = head;
// Initialize pointers
let prev = dummy;
let current = head;
// Step 1: Move the prev pointer to the node just before the 'left' position
for (let i = 0; i < left - 1; i++) {
prev = current;
current = current.next;
}
// Save the pointers to reconnect the reversed sublist
let lastUnswappedNode = prev;
let firstNodeOfSublist = current;
// Step 2: Reverse the sublist from 'left' to 'right'
prev = null;
for (let i = 0; i < right - left + 1; i++) {
let nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Step 3: Reconnect the reversed sublist with the rest of the list
lastUnswappedNode.next = prev;
firstNodeOfSublist.next = current;
return dummy.next;
};Solution in Java:
Java
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// Edge case: if the list is empty or left == right, no need to reverse
if (head == null || left == right) {
return head;
}
// Create a dummy node to simplify edge cases
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize pointers
ListNode prev = dummy;
ListNode current = head;
// Step 1: Move the prev pointer to the node just before the 'left' position
for (int i = 0; i < left - 1; i++) {
prev = current;
current = current.next;
}
// Save the pointers to reconnect the reversed sublist
ListNode lastUnswappedNode = prev;
ListNode firstNodeOfSublist = current;
// Step 2: Reverse the sublist from 'left' to 'right'
prev = null;
for (int i = 0; i < right - left + 1; i++) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Step 3: Reconnect the reversed sublist with the rest of the list
lastUnswappedNode.next = prev;
firstNodeOfSublist.next = current;
return dummy.next;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseBetween(ListNode head, int left, int right) {
// Edge case: if the list is empty or left == right, no need to reverse
if (head == null || left == right) {
return head;
}
// Create a dummy node to simplify edge cases
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize pointers
ListNode prev = dummy;
ListNode current = head;
// Step 1: Move the prev pointer to the node just before the 'left' position
for (int i = 0; i < left - 1; i++) {
prev = current;
current = current.next;
}
// Save the pointers to reconnect the reversed sublist
ListNode lastUnswappedNode = prev;
ListNode firstNodeOfSublist = current;
// Step 2: Reverse the sublist from 'left' to 'right'
prev = null;
for (int i = 0; i < right - left + 1; i++) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Step 3: Reconnect the reversed sublist with the rest of the list
lastUnswappedNode.next = prev;
firstNodeOfSublist.next = current;
return dummy.next;
}
}