**π‘ 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.