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

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.