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

Rate this post

πŸ’‘ 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.