# 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

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

# Alternate nodes from front and stack
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

```

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
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

# Find the midpoint of the linked list using slow and fast pointers
while fast and fast.next:
slow = slow.next
fast = fast.next.next

second_half = reverse_list(slow.next)
slow.next = None

# Example usage
# Assuming previous example list is used
```

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

# Function to find middle and split list into two equal halves
while fast and fast.next:
slow = slow.next
fast = fast.next.next
middle = slow.next
slow.next = None

return helper(front, back)

# Example usage
# Assuming previous example list is used
```

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

# Initialize two pointers

# 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

# 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

# Example usage with the same list as in the previous examples
```

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.