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

Rate this post

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

stack = []

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

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

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

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

if proceed:
return (None, False)

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

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

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

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

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

while current:
length += 1
current = current.next
return length

middle = length // 2

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

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

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

dq = deque()

head = dq.popleft() if dq else None

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

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
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.