How to flatten a linked list

A linked list is a commonly used data structure made up of nodes interlinked using pointers.

Note: Read more about linked lists here.

Multi-dimensional linked list

A linked list can be multi-dimensiona,l i.e., each node can have a child node in addition to a next pointer. The process of converting a multi-dimensional linked list into a single dimension one is called flattening.

Flattening a linked list

To flatten a linked list, we need to go through the children of a node first before moving on to its next node. The following algorithm would be used:

Make two pointers that point at the head initially.
If a node has a child node, store the next node in a variable and change the child node to be the next node.
Repeat this for the child node until we reach the end of the list. Once that happens, point the next pointer of that node to the node after the original parent node.
Repeat this until we reach the end of the list.

Example

class Node:
  def __init__(self, val, next=None, child=None):
    self.val = val
    self.next = next
    self.child = child
class LinkedList:
  def __init__(self, node=None):
    self.head = node
  
  def flatten(self):
    self._flatten(self.head)
  
  def _flatten(self, head):
    if not head:
      return None
    if not head.child and not head.next:
      return head
    if not head.child:
      return self._flatten(head.next)
    
    next_node = head.next
    head.next = head.child
    head.child = None
    joining_node = self._flatten(head.next)
    if joining_node:
      joining_node.next = next_node
    return self._flatten(next_node)
# creating a list
a = LinkedList()
a.head = Node(1)
a.head.next = Node(2)
a.head.next.next = Node(3)
a.head.next.next.next = Node(4)
a.head.next.next.next.next = Node(5)
a.head.next.next.child = Node(7)
a.head.next.next.child.next = Node(8)
a.head.next.next.child.next.next = Node(9)
a.head.next.next.child.next.child = Node(11)
a.flatten() # calling flatten
# printing the values in order
node = a.head
while node.next:
  print(node.val, end=' -> ')
  node = node.next
print(node.val)

Explanation

Lines 1–5: A class Node is defined in which each node has a next pointer and a child pointer.
Lines 11–12: The function flatten() calls the helper function _flatten() and initially provides it with the root node.
Lines 15–20: We check if a node is None or if a node has a child and/or a next node and then return appropriate values respectively.
Lines 31–49: We create a multi-dimensional linked list manually and then call the flatten() function on it. In the end, we print all the values of the one-dimensional list in order.

Free Resources