Reverse Linked List II

class Solution {
public:
    ListNode* reverseSection(ListNode* start, int left, int right) {
        if (!start) {
            return nullptr;
        }
        ListNode *current = start, *previous = nullptr;
        while (left > 1) {
            previous = current;
            current = current->next;
            left--;
            right--;
        }
        ListNode *connection = previous, *tail = current;
        ListNode* temp = nullptr;
        while (right > 0) {
            temp = current->next;
            current->next = previous;
            previous = current;
            current = temp;
            right--;
        }
        if (connection != nullptr) {
            connection->next = previous;
        } else {
            start = previous;
        }
        tail->next = current;
        return start;
    }
};

This article presents a solution to reverse a subsection of a singly linked list using C++.

• The solution employs a single pass approach to the linked list, achieving an efficient manner to reverse nodes between specified positions left and right.
• The function reverseSection is initiated with a pointer to the starting node of the linked list and two integers, left and right, defining the bounds within which the list should be reversed.

Furthermore, the function reverseSection performs the steps below:

1. Initialize a pointer current to travel from the start of the list to the position left.
2. Use a previous pointer to assist in reversing the links between the nodes from position left to right.
3. current advances through the linked list while previous assists in reversing the connections until the sub-list is fully traversed.
4. Maintain pointers connection and tail to handle the un-reversed parts of the linked list's start and end respectively.
5. After the sub-list is reversed, connection and tail are connected to the now reversed sub-list appropriately, ensuring a smooth transition and rearrangement within the linked list.
6. Finally, check and handle edge cases such as when the reverse happens at the beginning of the list.

In essence, this solution efficiently performs the reversal of the linked list section in place, facilitating a straightforward approach in solving node re-arrangement tasks in linked data structures. This method maintains the integrity of the entire list while effectively modifying only the targeted section.

class Solution {
    public ListNode reverseSublist(ListNode startNode, int left, int right) {
        if (startNode == null) return null;
    
        ListNode current = startNode, previous = null;
        while (left > 1) {
            previous = current;
            current = current.next;
            left--;
            right--;
        }
    
        ListNode connection = previous, sublist_tail = current;
        ListNode tmp = null;
        while (right > 0) {
            tmp = current.next;
            current.next = previous;
            previous = current;
            current = tmp;
            right--;
        }
    
        if (connection != null) {
            connection.next = previous;
        } else {
            startNode = previous;
        }
    
        sublist_tail.next = current;
        return startNode;
    }
}

The provided Java solution involves a method to reverse a specific part of a singly linked list between two given positions. The method reverseSublist accepts a ListNode representing the start of the list and two integers left and right indicating the positions of the segment to reverse. The reversal only affects the nodes between these positions inclusively.

Key steps in the implementation:

• Initialize pointers current to the start of the list and previous to null.
• Traverse the list until the current pointer reaches the left position, updating current and previous accordingly.
• Mark the node before the left position as connection and the first node of the sub-list that needs to be reversed as sublist_tail.
• Continue traversing and reversing the links between current and previous until reaching the end of the sub-list defined by right.
• Adjust the next pointers:
  • Link the connection node to the previous, effectively pointing it to the last node of the reversed sub-list.
  • Connect the tail of the reversed sub-list (sublist_tail) to the current, which marks the node following the reversed portion.
• If the reversed sub-list includes the first node (i.e., left is 1), update the head of the list.
• Return the modified list.

Considerations:

• The function handles edge cases like null input by returning null.
• Properly updates connections for segments starting from the head and ensures the remaining list portions are correctly connected post reversal.

struct ListNode *reverseSublist(struct ListNode *head, int start, int end) {
    if (!head) {
        return NULL;
    }
    struct ListNode *current = head, *previous = NULL;
    while (start > 1) {
        previous = current;
        current = current->next;
        start--;
        end--;
    }
    struct ListNode *connection = previous, *sublist_tail = current;
    struct ListNode *next_node = NULL;
    while (end > 0) {
        next_node = current->next;
        current->next = previous;
        previous = current;
        current = next_node;
        end--;
    }
    if (connection)
        connection->next = previous;
    else
        head = previous;
    sublist_tail->next = current;
    return head;
}

In the C programming code provided, the function reverseSublist effectively reverses a section of a singly linked list defined between two given positions, start and end. This function handles edge cases, like an empty list input, and operates directly on the list nodes to adjust pointers and reverse the sublist without creating a new list. Here's a walkthrough of how the function operates:

1. Start by checking if the head pointer is NULL. If it is, return NULL, as there's no list to process.
2. Establish a current pointer to traverse the linked list and a previous pointer set to NULL to help in the reversal.
3. Navigate to the start of the sublist using a loop, updating the current and previous pointers, decrementing both start and end to keep track of the positions.
4. Keep a pointer connection pointing to just before the start of the sublist part and sublist_tail pointing at the start of this sublist before the reversal.
5. Continue the traversal. For each node in the sublist, make its next pointer point to the previous node effectively reversing the connections between the nodes.
6. Once the sublist is reversed, adjust the next pointers of connection and sublist_tail to connect the reversed sublist with the non-reversed parts of the original linked list.
7. If the reversed part extends to the head of the list, update the head otherwise reconnect the reversed part to the main list using the connection pointer.

Finally, the function correctly reconnects the last node of the reversed sublist (sublist_tail) to the current node, addressing potential disconnections in the linked list chain. The result is the original list with the specified section reversed, and the function returns the possibly new head of the list if the reversal included the first node.

var reverseSublist = function (listHead, start, end) {
    if (listHead === null) {
        return null;
    }
    let current = listHead,
        previous = null;
    while (start > 1) {
        previous = current;
        current = current.next;
        start--;
        end--;
    }
    let connection = previous,
        sublistTail = current;
    let temp = null;
    while (end > 0) {
        temp = current.next;
        current.next = previous;
        previous = current;
        current = temp;
        end--;
    }
    if (connection !== null) {
        connection.next = previous;
    } else {
        listHead = previous;
    }
    sublistTail.next = current;
    return listHead;
};

The provided JavaScript solution implements a function to reverse a specified portion of a linked list. Here's a breakdown of how the algorithm works:

• Initialize pointers: The function starts by checking if the provided linked list head (listHead) is null. If it is, return null as the list cannot be reversed.

• Find the sublist: Set current to point to the head of the list and move it along with a previous pointer until reaching the position where reversal should start.

• Reverse sublist: Utilize a while loop to reverse the nodes between the specified start and end positions. This involves adjusting node pointers within the sublist.

• Reconnect sublist: After reversing the sublist, reconnect the reversed sublist with the rest of the linked list. If the sublist starts at the head, update listHead. Otherwise, link the previous part of the list to the new start of the sublist.

• Handle the tail of the sublist: Link the tail of the reversed sublist (sublistTail) to the node current which is where the reversing ended.

Finally, the function returns the modified list head with the specified sublist reversed. This approach leverages pointer manipulation to perform the reversal in-place, ensuring an efficient solution with constant space complexity. Be sure to update the pointers correctly to avoid common errors such as losing links or creating cycles in the linked list.

class Solution:
    def reverseSublist(
        self, start: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        if not start:
            return None
    
        current, previous = start, None
        while left > 1:
            previous = current
            current = current.next
            left, right = left - 1, right - 1
    
        sublist_tail, sublist_conn = current, previous
    
        while right:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
            right -= 1
    
        if sublist_conn:
            sublist_conn.next = previous
        else:
            start = previous
        sublist_tail.next = current
        return start

This solution implements a function to reverse a sublist within a singly linked list in Python. To reverse a segment of the list designated by left and right indices, follow this approach:

1. Initialize pointers current to the starting node and previous to None.
2. Traverse the list until current points to the left-th node, adjusting previous accordingly. This sets up the start of the sublist to reverse.
3. Use two more pointers sublist_tail and sublist_conn to help reconnect the reversed sublist. sublist_tail initially points to the node at position left and sublist_conn to the node just before left.
4. Commence the sublist reversal by iterating until right becomes zero. In each iteration, adjust the next pointers to reverse the links.
5. Connect the reversed sublist back to the main list:
   • If there was a node before the sublist (sublist_conn is not None), link it to previous which now points to the first node of the reversed sublist.
   • If sublist_conn is None, it indicates the sublist includes the first node of the list, so update the start of the list to previous.
   • Connect the original sublist_tail to the node current now points to, which is the node right after the last reversed node.
6. Return start as the new head of potentially modified list.

This solution ensures that only the specified segment of the list is reversed and properly connected back, maintaining the integrity of the list structure while performing the modifications in-place.