# 5 Best Ways to Find a Folded List from a Given Linked List in Python

π‘ Problem Formulation: In the realm of data structures, a linked list fold is a transformation where the list is divided into two parts, and the second part is reversed and paired with the first. Given a singly linked list, the challenge is to compute the folded linked list. For example, if the input linked list is `1->2->3->4->5`, the folded list would be `1->5->2->4->3`.

## Method 1: Iterative Approach with Stack

An iterative approach to folding a linked list in Python involves traversing the list with two pointers, one moving twice the speed of the other, to find the midpoint. Subsequently, the second half is pushed onto a stack. Finally, nodes are popped from the stack and woven with the first half to create the folded list.

Here’s an example:

```class ListNode:
def __init__(self, value=0, next=None):
self.val = value
self.next = next

def fold_list(head):
slow, fast = head, head
stack = []

while fast and fast.next:
slow = slow.next
fast = fast.next.next

while slow:
stack.append(slow)
slow = slow.next

current = head
while stack:
temp = stack.pop()
temp.next = current.next
current.next = temp
current = temp.next.next

if current:
current.next = None

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
fold_list(head)```

The output will be the folded linked list: `1->5->2->4->3`

This code snippet defines a `ListNode` class representing an element of a singly linked list and a function `fold_list` that manipulates the list to fold it. Using two pointers, ‘slow’ and ‘fast’, we find the middle of the list. Then, the second half of the list is stored in a stack. Subsequently, we weave the nodes from the stack with the first half. The result is a folded linked list.

## Method 2: Recursive Approach

The recursive approach for folding a linked list is more concise but trades off space for system call stack. The recursion mimics the iterative approach, finding the middle and weaving the nodes from the end back into the front, accomplished through backtracking inherent to the recursive calls.

Here’s an example:

```class ListNode:
# ListNode class definition same as before

def fold_list_recursive(head, current=None):
if not head:
return head
if not head.next:
return (head, head.next != current)

tail, proceed = fold_list_recursive(head.next, current if current else head)
if proceed:
tail.next, head.next = head.next, tail
return (tail.next, head != current)
return (None, False)

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
fold_list_recursive(head)```

The output will be the folded linked list: `1->5->2->4->3`

This recursive implementation defines the `fold_list_recursive` function, which internally takes the current node to weave from the end into the front as it backtracks. The base case handles the reversal of the nodes at the end of the list, and through recursive calls, the nodes are folded correctly, leading to a folded list.

## Method 3: In-Place Reversal and Merge

This method involves first reversing the second half of the linked list in place and then merging the two halves. This approach has the advantage of using constant space as it alters the list nodes’ pointers without auxiliary data structures like stacks or recursion.

Here’s an example:

```class ListNode:
# ListNode class definition same as before

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

def fold_list_in_place(head):
slow, fast = head, head
prev_node = None

while fast and fast.next:
prev_node = slow
slow = slow.next
fast = fast.next.next

prev_node.next = None  # Break the list into two halves
second_half = reverse_list(slow)  # Reverse the second half

# Merge the two halves
first_half, current = head, None
while first_half and second_half:
temp1, temp2 = first_half.next, second_half.next
current = first_half if not current else current.next
current.next, second_half.next = second_half, temp1
first_half, second_half = temp1, temp2

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
fold_list_in_place(head)```

The output will be the folded linked list: `1->5->2->4->3`

The `fold_list_in_place` function separates the list by cutting it at the midpoint. The `reverse_list` function is used to reverse the second half of the list. The nodes of the two halves are then alternately merged to achieve a folded structure without using any additional space.

## Method 4: Using Length of the Linked List

This method entails first determining the length of the linked list and then folding the list based on the index of each node, which is determined by traversing the list. By using the list’s length, we can control the folding process more explicitly.

Here’s an example:

```class ListNode:
# ListNode class definition same as before

def get_length(head):
length, current = 0, head
while current:
length += 1
current = current.next
return length

def fold_list_with_length(head):
length = get_length(head)
middle = length // 2

prev, current = None, head
for _ in range(middle):
prev, current = current, current.next

prev.next = None  # Seperate the list into two

# Tail insert the nodes from the second half to the first
while current:
temp = current.next
current.next = head.next
head.next = current
current = temp
head = head.next.next

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
fold_list_with_length(head)```

The output will be the folded linked list: `1->5->2->4->3`

The `get_length` function computes the total count of nodes. The `fold_list_with_length` function utilizes this count to split the list at the middle. Thereafter, the list is folded by alternating insertions from the second half into the first, ensuring the nodes are placed correctly according to the length of the list.

## Bonus One-Liner Method 5: Using List Comprehension and Deque

This one-liner approach converts the linked list to a deque and utilizes list comprehension in conjunction with Python’s deque operations to achieve the fold. While concise, this method does not operate on the linked list directly but rather on a deque that is built from the list.

Here’s an example:

```from collections import deque

class ListNode:
# ListNode class definition same as before

def folded_list_one_liner(head):
dq = deque()

while head:
dq.append(head)
head = head.next

head = dq.popleft() if dq else None
current = head

while dq:
if current:
current.next = dq.pop()
current = current.next
if dq:
current.next = dq.popleft()
current = current.next
if current:
current.next = None

return head

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
folded_list_one_liner(head)```

The output will be the folded linked list: `1->5->2->4->3`.

The one-liner `folded_list_one_liner` function builds a deque `dq` from the linked list nodes. Utilizing the `popleft` and `pop` methods offered by deque, the function performs the necessary left and right insertions to construct the folded list in a concise and Pythonic way.

## Summary/Discussion

• Method 1: Iterative Approach with Stack. While intuitive, it incurs extra memory for the stack.
• Method 2: Recursive Approach. Offers a more elegant solution but is not space-efficient due to recursion call stack.
• Method 3: In-Place Reversal and Merge. More memory efficient as it does not use additional data structures, but can be slightly complex to understand.
• Method 4: Using Length of the Linked List. Explicit control of node placements based on index; simple conceptually but requires two passes over the list.
• Bonus Method 5: Using List Comprehension and Deque. This is a one-liner, more Pythonic solution but requires conversion from the linked list data structure to a deque.