5 Best Ways to Convert Linked List by Alternating Nodes from Front and Back in Python

Rate this post

πŸ’‘ Problem Formulation: This article addresses the challenge of restructuring a singly linked list such that its elements are reordered in an alternating pattern between nodes from the front and the back of the list. In other words, if the input linked list is 1->2->3->4->5->6, the desired output after conversion would be 1->6->2->5->3->4.

Method 1: Using a Stack for Reversal

This method involves iterating through the linked list to push all nodes onto a stack. The Last-In-First-Out nature of a stack ensures that nodes can be popped off in reverse order. The original linked list is traversed a second time while nodes are popped from the stack and inserted back into the list in an alternating pattern.

Here’s an example:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def alternate_from_stack(head):
    # Push nodes to stack
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next

    # Alternate nodes from front and stack
    current = head
    while stack:
        if current.next == stack[-1]:
            break
        stack_top = stack.pop()
        stack_top.next = current.next
        current.next = stack_top
        current = stack_top.next

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)

alternate_from_stack(head)

Output after running the code:

1->6->2->5->3->4

The stack-based method provides a clear approach to reversing the second half of the list for alternation and works by reconstructing the list on the go. While this is straightforward, the drawback is that it requires O(n) extra space for the stack.

Method 2: In-Place Reversal and Merge

In this approach, the linked list is split into two halves; the second half is reversed in place, and then both halves are merged into one with an alternating pattern. This method is more space-efficient as it works in-place without requiring additional storage.

Here’s an example:

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

def merge_alternate(a, b):
    dummy = Node(0)
    tail = dummy
    while a and b:
        tail.next = a
        a = a.next
        tail = tail.next

        tail.next = b
        b = b.next
        tail = tail.next
    
    if a: tail.next = a
    if b: tail.next = b
    return dummy.next

def alternate_in_place(head):
    # Find the midpoint of the linked list using slow and fast pointers
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    second_half = reverse_list(slow.next)
    slow.next = None
    return merge_alternate(head, second_half)

# Example usage
# Assuming previous example list is used
new_head = alternate_in_place(head)

Output after running the code:

1->6->2->5->3->4

This method is an efficient and neat way to perform the task in terms of space complexity O(1) as it does not rely on extra data structures. However, it is slightly more complex with multiple steps such as splitting, reversing, and merging.

Method 3: Recursion

Utilizing the recursion strategy, this technique seeks to restructure the linked list by reaching the end of the list recursively and then weaving the nodes on the return trip, effectively alternating the nodes without explicit reversal of the list.

Here’s an example:

def helper(front, back):
    if not back:
        return front

    next_front = front.next
    next_back = back.next
    front.next = back
    back.next = helper(next_front, next_back)

    return front

def alternate_recursive(head):
    # Function to find middle and split list into two equal halves
    def split_list(head):
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        middle = slow.next
        slow.next = None
        return head, middle

    front, back = split_list(head)
    return helper(front, back)

# Example usage
# Assuming previous example list is used
new_head = alternate_recursive(head)

Output after running the code:

1->6->2->5->3->4

Recursion provides a clean and elegant solution. However, it might not be the most efficient due to the stack space used for recursive calls, and it might lead to stack overflow for large lists.

Method 4: Iterative Pointers Movement

This method relies on the concept of simultaneously moving two pointers at different rates through the linked list, effectively splitting the list into two by weaving nodes from each side together in an alternating pattern without an explicit need for reversal.

Here’s an example:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
def alternate_iterative(head):
    # Initialize two pointers
    prev_slow = head
    slow = head
    fast = head.next
    
    # Split the linked list into two halves
    while (fast and fast.next):
        prev_slow = slow
        slow = slow.next
        fast = (fast.next).next

    second = slow.next
    slow.next = None
    first = head
    
    # Now 'first' and 'second' represent the two halves
    # Start weaving the two lists
    while (first is not None and second is not None):
        temp1 = first.next
        temp2 = second.next

        first.next = second
        second.next = temp1

        first = temp1
        second = temp2
    return head

# Example usage with the same list as in the previous examples
new_head = alternate_iterative(head)

Output after running the code:

1->6->2->5->3->4

The iterative pointer movement method is a straightforward solution that involves no recursion and no extra space. However, getting the pointer movements correct can be tricky, and any mistakes can lead to a corrupted list.

Bonus One-Liner Method 5: Using List Comprehension

This method calculates the midpoint of the linked list and uses slicing to create two separate lists. Then, using Python’s list comprehension and zip function, it interleaves the two lists. This method heavily relies on Python’s built-in functions and list manipulation features. It does assume that the list is converted to a regular Python list first, which can then be converted back to a linked list.

Here’s an example:

# Assuming the linked list has been converted into a regular Python list 'nodes'
nodes = [1, 2, 3, 4, 5, 6]
mid = len(nodes) // 2
front = nodes[:mid]
back = nodes[mid:][::-1]

# One-liner to interleave the lists
interleaved = [node for pair in zip(front, back) for node in pair]

# After interleaving, convert 'interleaved' back into a linked list

Output after running the one-liner:

[1, 6, 2, 5, 3, 4]

This one-liner approach is more of a Pythonic trick rather than a typical algorithm for linked lists. It’s a quick and easy solution but entails converting the linked list to a list and back, which can be expensive for large lists.

Summary/Discussion

  • Method 1: Using a Stack for Reversal. Straightforward, but requires O(n) extra space.
  • Method 2: In-Place Reversal and Merge. Space-efficient in terms of O(1), albeit multipart approach.
  • Method 3: Recursion. Elegant, but not suitable for large lists due to potential stack overflow.
  • Method 4: Iterative Pointers Movement. No extra space or recursion, but implementation can be complicated.
  • Bonus One-Liner Method 5: List Comprehension and Zip. Pythonic and concise, not suitable for traditional linked list manipulation.