Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Move from brute-force thinking to an efficient approach using linked list strategy.
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:
n.1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= nProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Linked List
[1,2,3,4,5] 2 4
[5] 1 1
reverse-linked-list)/**
* Definition for singly-linked list.
* public 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 reverseBetween(ListNode head, int left, int right) {
if (head == null || left == right) return head;
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
for (int i = 1; i < left; i++) prev = prev.next;
ListNode cur = prev.next;
for (int i = 0; i < right - left; i++) {
ListNode move = cur.next;
cur.next = move.next;
move.next = prev.next;
prev.next = move;
}
return dummy.next;
}
}
/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head == nil || left == right {
return head
}
dummy := &ListNode{Val: 0, Next: head}
prev := dummy
for i := 1; i < left; i++ {
prev = prev.Next
}
cur := prev.Next
for i := 0; i < right-left; i++ {
move := cur.Next
cur.Next = move.Next
move.Next = prev.Next
prev.Next = move
}
return dummy.Next
}
# 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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head or left == right:
return head
dummy = ListNode(0, head)
prev = dummy
for _ in range(left - 1):
prev = prev.next
cur = prev.next
for _ in range(right - left):
move = cur.next
cur.next = move.next
move.next = prev.next
prev.next = move
return dummy.next
/**
* Definition for singly-linked list.
* #[derive(PartialEq, Eq, Clone, Debug)]
* pub struct ListNode {
* pub val: i32,
* pub next: Option<Box<ListNode>>
* }
* impl ListNode {
* #[inline]
* fn new(val: i32) -> Self {
* ListNode { next: None, val }
* }
* }
*/
impl Solution {
pub fn reverse_between(head: Option<Box<ListNode>>, left: i32, right: i32) -> Option<Box<ListNode>> {
let mut vals = Vec::new();
let mut cur = head;
while let Some(mut node) = cur {
vals.push(node.val);
cur = node.next.take();
}
let l = (left - 1) as usize;
let r = (right - 1) as usize;
vals[l..=r].reverse();
let mut out = None;
for &v in vals.iter().rev() {
out = Some(Box::new(ListNode { val: v, next: out }));
}
out
}
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
if (!head || left === right) return head;
const dummy = new ListNode(0, head);
let prev: ListNode = dummy;
for (let i = 1; i < left; i++) prev = prev.next!;
let cur = prev.next!;
for (let i = 0; i < right - left; i++) {
const move = cur.next!;
cur.next = move.next;
move.next = prev.next;
prev.next = move;
}
return dummy.next;
}
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.