Problem 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.

Problem Link

Solution 1: Two Pointers

We can use two pointers to solve this issue. The key point is how to reverse the sublist between left and right.

Code

func reverseBetween(head *ListNode, left, right int) *ListNode {
    if head == nil || left == right {
        return head
    }
    dummy := &ListNode{Next: head}
    prev := dummy
    for i := 1; i < left; i++ {
        prev = prev.Next
    }
    current := prev.Next
    
    for i := 0; i < right - left; i++ {
        nextNode := current.Next
        current.Next = nextNode.Next
        nextNode.Next = prev.Next
        prev.Next = nextNode
    }
    
    return dummy.Next
    
}

Solution 2: Recursion

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == 1 {
        return reverseN(head, right)
    }
    head.Next = reverseBetween(head.Next, left-1, right-1)
    return head
}

func reverseN(head *ListNode, n int) *ListNode {
    if n == 1 {
        return head
    }
    last := reverseN(head.Next, n-1)
    successor := head.Next.Next
    head.Next.Next = head
    head.Next = successor
    return last
}