Reverse Linked List Ii

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode* curr = pre->next;
        for (int i = 0; i < right - left; i++) {
            ListNode* temp = pre->next;
            pre->next = curr->next;
            curr->next = curr->next->next;
            pre->next->next = temp;
        }
        return dummy->next;
    }
};

                                            
/**
 * 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) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        
        ListNode curr = pre.next;
        for (int i = left; i < right; i++) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        
        return dummy.next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    if(left == right) return head;
    
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = -1;
    dummy->next = head;
    
    struct ListNode* prev = dummy;
    
    for(int i = 0; i < left - 1; i++) {
        prev = prev->next;
    }
    
    struct ListNode* curr = prev->next;
    struct ListNode* next;
    
    for(int i = 0; i < right - left; i++) {
        next = curr->next;
        curr->next = next->next;
        next->next = prev->next;
        prev->next = next;
    }
    
    return dummy->next;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 */
public class Solution {
    public ListNode ReverseBetween(ListNode head, int left, int right) {
        ListNode prev = null;
        ListNode curr = head;
        int count = 1;

        while (count < left) {
            prev = curr;
            curr = curr.next;
            count++;
        }

        ListNode con = prev;
        ListNode tail = curr;

        while (count <= right) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
            count++;
        }

        if (con != null) {
            con.next = prev;
        } else {
            head = prev;
        }

        tail.next = curr;

        return head;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 */
var reverseBetween = function(head, left, right) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    
    for(let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    
    let current = prev.next;
    for(let i = 0; i < right - left; i++) {
        let temp = prev.next;
        prev.next = current.next;
        current.next = current.next.next;
        prev.next.next = temp;
    }
    
    return dummy.next;
};

                                            
/**
 * 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) {
        return null;
    }
    
    let dummy = new ListNode();
    dummy.next = head;
    let prev = dummy;

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

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

    return dummy.next;
};

                                            
class Solution {

    /**
     * Definition for a singly-linked list.
     * class ListNode {
     *     public $val = 0;
     *     public $next = null;
     *     function __construct($val = 0, $next = null) {
     *         $this->val = $val;
     *         $this->next = $next;
     *     }
     * }
     */

    function reverseBetween($head, $left, $right) {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $prev = $dummy;

        for ($i = 0; $i < $left - 1; $i++) {
            $prev = $prev->next;
        }

        $current = $prev->next;
        for ($i = 0; $i < $right - $left; $i++) {
            $temp = $prev->next;
            $prev->next = $current->next;
            $current->next = $current->next->next;
            $prev->next->next = $temp;
        }

        return $dummy->next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

class Solution {
    func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        var prev: ListNode? = nil
        var curr: ListNode? = head
        var start: ListNode? = head
        var position = 1
        
        while position < left {
            prev = curr
            curr = curr?.next
            start = start?.next
            position += 1
        }
        
        var end: ListNode? = curr
        while position < right {
            let next = end?.next
            end?.next = next?.next
            if let n = next {
                next?.next = start
                start = next
            }
            position += 1
        }
        
        if prev == nil {
            return start
        } else {
            prev?.next = start
            return head
        }
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
        if (head == null) return null
        
        var dummy = ListNode(0)
        dummy.next = head
        var pre = dummy
        
        for (i in 1 until left) {
            pre = pre.next
        }
        
        var start = pre.next
        var then = start?.next
        
        for (i in left until right) {
            start?.next = then?.next
            then?.next = pre?.next
            pre?.next = then
            then = start?.next
        }
        
        return dummy.next
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    prev := dummy
    for i := 0; i < left-1; i++ {
        prev = prev.Next
    }
    curr := prev.Next
    for i := 0; i < right-left; i++ {
        next := curr.Next
        curr.Next = next.Next
        next.Next = prev.Next
        prev.Next = next
    }
    return dummy.Next
}

                                            
class ListNode
    attr_accessor :val, :next
    def initialize(val = 0, _next = nil)
        @val = val
        @next = _next
    end
end

def reverse_between(head, left, right)
    dummy = ListNode.new(0)
    dummy.next = head
    prev_left = dummy
    
    (left - 1).times do
        prev_left = prev_left.next
    end
    
    current = prev_left.next
    (right - left).times do
        temp = current.next
        current.next = temp.next
        temp.next = prev_left.next
        prev_left.next = temp
    end
    
    return dummy.next
end

To solve this coding challenge, we need to reverse a section of a linked list from position

left

right

. Here is a very detailed explanation and pseudocode for solving this problem:

Explanation

We begin by examining the given linked list and determining the section that needs to be reversed. The aim is to manipulate the pointers of the linked list nodes such that only the nodes between positions

left

and

right

are reversed, while the rest of the list remains unchanged.

Step-by-Step Explanation:

Initialization : We employ a dummy node to simplify edge cases, such as reversing from the first node. The dummy node will initially point to the head of the list. We also initialize a pointer,
prev

, to traverse the list up to the node just before the
left

position.
Traverse to the Start : Move
prev

to the node immediately before position
left

. Typically, this requires
left-1

moves from the dummy node.
Reverse the Target Segment :

Use a pointer,
current

, which starts at the
left

position.
Perform multiple swaps to reverse the segment from
left

to
right

.
We achieve this by iterative pointer reassignments within the determined range, effectively reversing the required segment of the list.

Complete the List : After the reversal segment, connect the reversed sublist back to the remaining parts of the list.
Return the New Head : Finally, the new head of the modified list is the next node of the dummy node since the head node might have been changed during the reversal process.

Detailed Steps in Pseudocode

Below, we provide the pseudocode with detailed explanations embedded within the comments.

Pseudocode Steps:

                                            
# Define a function that accepts the head of the linked list and two integers, left and right
function reverseSection(head, left, right):
    # Create a dummy node that simplifies edge cases; the dummy node points to head initially
    dummy_node = new ListNode(0)
    dummy_node.next = head
    
    # Initialize a pointer, 'prev', to start from the dummy node
    prev_node = dummy_node

    # Move 'prev' to the node just before the 'left' position
    for i from 1 to left-1:
        prev_node = prev_node.next

    # 'current_node' points to the start of the segment to be reversed
    current_node = prev_node.next

    # Reverse the sublist from 'left' to 'right'
    for i from left to right-1:
        # Store the next node of 'current_node' temporarily
        next_node_temp = current_node.next
        
        # Adjust pointers to reverse the segment
        current_node.next = next_node_temp.next
        next_node_temp.next = prev_node.next
        prev_node.next = next_node_temp

    # Return the next node of dummy node, which is the new head of the list
    return dummy_node.next

# Example usage:
# head = [1,2,3,4,5], left = 2, right = 4
# Output should be [1,4,3,2,5]

By following these steps, you can reverse a specified part of a singly linked list while maintaining the order of the remaining elements. The solution is efficient, operating in O(n) time complexity, where n is the number of nodes in the linked list, and it uses O(1) additional space apart from the input list itself, as it only manipulates pointers within the list.