# 5 Best Ways to Reverse Inner Nodes of a Linked List in Python

π‘ 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

while current.next.next:
next_node = current.next
current.next = next_node.next
next_node.next = prev.next
prev.next = next_node

# Helper function to convert list to linked list
for val in lst[1:]:
current.next = ListNode(val)
current = current.next

# Helper function to display linked list
print('None')

# Execute the function
ll = list_to_linked_list([1, 2, 3, 4, 5])
reversed_ll = reverse_inner_nodes(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_until(node, last):
if node == last or node.next == last:
return last
first = reverse_until(node.next, last)
node.next.next = node
return first

while last.next:
last = last.next

# ... (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)

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)

stack = []
while current.next:
stack.append(current)
current = current.next
while stack:
next_node = stack.pop()
next_node.next = current.next.next
current.next = next_node
current = next_node

# ... (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)

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)

values = []
while current.next:
values.append(current.value)
current = current.next
for value in reversed(values):
current.value = value
current = current.next

# ... (same helper functions as before)

# Execute the function
ll = list_to_linked_list([1, 2, 3, 4, 5])
reverse_inner_node_values(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 = []
while node:
values.append(node.value)
node = node.next
values[1:-1] = values[-2:0:-1]
for value in values:
node.value = value
node = node.next

# ... (same helper functions as before)

# Execute the function
ll = list_to_linked_list([1, 2, 3, 4, 5])
reverse_inner_nodes_slicing(ll)
Output: `1 -> 4 -> 3 -> 2 -> 5 -> None`