**π‘ Problem Formulation:** Linked lists are a fundamental data structure in computer science. A common challenge is reversing part of a linked list, specifically the inner nodes, excluding the first and last nodes. For instance, given a linked list `1 -> 2 -> 3 -> 4 -> 5`

, reversing the inner nodes would yield `1 -> 4 -> 3 -> 2 -> 5`

. This article explores various methods to achieve this in Python.

## Method 1: Iterative Approach

The iterative approach involves traversing the linked list and reversing the inner nodes in place. This method ensures that the boundaries are preserved while inverting adjacent elements starting from the second node up to the penultimate node. This approach has a time complexity of O(n) and does not require additional memory, making it an efficient solution.

Here’s an example:

class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def reverse_inner_nodes(head): if not head or not head.next or not head.next.next: return head prev, current = head, head.next while current.next.next: next_node = current.next current.next = next_node.next next_node.next = prev.next prev.next = next_node return head # Helper function to convert list to linked list def list_to_linked_list(lst): head = ListNode(lst[0]) current = head for val in lst[1:]: current.next = ListNode(val) current = current.next return head # Helper function to display linked list def print_linked_list(head): while head: print(f'{head.value} -> ', end='') head = head.next print('None') # Execute the function ll = list_to_linked_list([1, 2, 3, 4, 5]) reversed_ll = reverse_inner_nodes(ll) print_linked_list(reversed_ll)

**Output:** `1 -> 4 -> 3 -> 2 -> 5 -> None`

This code snippet defines a `ListNode`

class to represent a node in a linked list, followed by a function `reverse_inner_nodes()`

that reverses the inner nodes iteratively. Two helper functions are provided to convert a Python list to a linked list and to print the linked list, used to demonstrate the function’s use.

## Method 2: Recursive Approach

The recursive approach involves breaking down the problem into smaller subproblems by using a helper function that receives the second node and the last but one node to process the reversal recursively. This elegant solution, however, has more memory overhead due to the recursion call stack and may not be as efficient as the iterative method for large lists.

Here’s an example:

class ListNode: # ... (same as before) def reverse_inner_nodes_recursive(head): def reverse_until(node, last): if node == last or node.next == last: return last first = reverse_until(node.next, last) node.next.next = node return first if not head or not head.next or not head.next.next: return head last = head while last.next: last = last.next first = reverse_until(head.next, last) head.next.next = last head.next = first return head # ... (same helper functions as before) # Execute the function ll = list_to_linked_list([1, 2, 3, 4, 5]) reversed_ll = reverse_inner_nodes_recursive(ll) print_linked_list(reversed_ll)

**Output:** `1 -> 4 -> 3 -> 2 -> 5 -> None`

This snippet demonstrates a recursive solution. It includes a nested function `reverse_until()`

that aids with the process of reversing nodes until a certain node is encountered. The main function then calls this helper, adjusting the linked list connections to yield the desired reversed inner node order.

## Method 3: Using a Stack

Using a stack data structure allows us to store the values of the inner nodes and then pop them in reverse order. This approach requires extra space, with space complexity O(n) for the stack, and has a time complexity O(n) for pushing and popping operations. It is less memory-efficient than the iterative approach but can be easier to understand for some developers.

Here’s an example:

class ListNode: # ... (same as before) def reverse_inner_nodes_stack(head): stack = [] current = head.next while current.next: stack.append(current) current = current.next current = head while stack: next_node = stack.pop() next_node.next = current.next.next current.next = next_node current = next_node return head # ... (same helper functions as before) # Execute the function ll = list_to_linked_list([1, 2, 3, 4, 5]) reversed_ll = reverse_inner_nodes_stack(ll) print_linked_list(reversed_ll)

**Output:** `1 -> 4 -> 3 -> 2 -> 5 -> None`

This code makes use of a stack to reverse the inner nodes of a linked list. The process involves pushing the nodes on a stack and then reconstructing the list by popping the nodes off, which results in the reversed inner node sequence. The stack ensures that nodes are processed in LIFO (last-in-first-out) order.

## Method 4: Swapping Node Values

This method swaps the inner node values instead of actual nodes themselves, leaving the node structure intact. It traverses the list, collecting values and then replacing them in reverse order starting from the second node. This method avoids the complexities of changing node links but doesn’t work if there are repeated nodes or if the linked list node contains more complex data.

Here’s an example:

class ListNode: # ... (same as before) def reverse_inner_node_values(head): values = [] current = head.next while current.next: values.append(current.value) current = current.next current = head.next for value in reversed(values): current.value = value current = current.next return head # ... (same helper functions as before) # Execute the function ll = list_to_linked_list([1, 2, 3, 4, 5]) reverse_inner_node_values(ll) print_linked_list(ll)

**Output:** `1 -> 4 -> 3 -> 2 -> 5 -> None`

This snippet swaps the values of the nodes to reverse the inner node values. The nodes’ positions remain intact, only their stored values are changed. This method simplifies the reversal problem by treating it as an array reversal, but it is not suitable for all linked list scenarios, especially when nodes contain complex objects or the identity of nodes matters.

## Bonus One-Liner Method 5: Using Python’s Slicing

Python’s list slicing feature, while not directly applicable to linked lists, can be utilized by converting the linked list to an array, performing the reversal, and then converting back. This is a concise but indirect method that doesn’t operate on the linked list directly and involves extra steps that may not be practical for large linked lists or real-world applications where linked list operations should not depend on array constructs.

Here’s an example:

def reverse_inner_nodes_slicing(head): values = [] node = head while node: values.append(node.value) node = node.next values[1:-1] = values[-2:0:-1] node = head for value in values: node.value = value node = node.next return head # ... (same helper functions as before) # Execute the function ll = list_to_linked_list([1, 2, 3, 4, 5]) reverse_inner_nodes_slicing(ll) print_linked_list(ll)

**Output:** `1 -> 4 -> 3 -> 2 -> 5 -> None`

The one-liner in this example involves creating a list of values from the linked list, applying slicing to reverse the required segment of values, and then mapping the reversed values back to the linked list. This method offers the simplest code for readability but doesn’t adhere to the typical linked list operations, shedding light on the trade-offs between practical linked list manipulations and algorithmic purity.

## Summary/Discussion

**Method 1:**Iterative Approach. The iterative method is efficient and straightforward, with no additional memory overhead. However, it could be more complex for newcomers to grasp, especially in managing pointers.**Method 2:**Recursive Approach. The recursive method is elegant and can be easier to understand but it is less memory-efficient due to the recursion call stack, and it’s suitable for lists that are not too large.**Method 3:**Using a Stack. This method has an intuitive approach, but it requires additional memory for the stack, making it less suitable for memory-constrained environments.**Method 4:**Swapping Node Values. This approach simplifies the reversal problem to a value-based one. However, it may not be valid in all scenarios, especially when nodes have more complex data.**Bonus Method 5:**Using Python’s Slicing. A concise solution that reads well but strays from pure linked list manipulation, which can be limiting for certain linked list applications.