5 Best Ways to Add Corresponding Positioned Elements of 2 Linked Lists in Python

Rate this post

πŸ’‘ Problem Formulation: When working with data structures in Python, a common problem is how to efficiently add together elements from two linked lists that have the same position within the lists. For instance, given two linked lists, list1: 1 -> 2 -> 3 and list2: 4 -> 5 -> 6, the desired output after addition would be a new linked list: 5 -> 7 -> 9.

Method 1: Iterative Approach

This method involves traversing both linked lists in a synchronized manner using an iterative loop. At each step, the data values of the current nodes are added, and a new node with the summed value is added to the result list. The function maintains a pointer to the last node in the result list for efficient additions.

Here’s an example:

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

def add_linked_lists(head1, head2):
    dummy = ListNode()
    tail = dummy
    carry = 0
    
    while head1 or head2 or carry:
        val1 = (head1.value if head1 else 0)
        val2 = (head2.value if head2 else 0)
        carry, out = divmod(val1 + val2 + carry, 10)
        
        tail.next = ListNode(out)
        tail = tail.next
        
        if head1: head1 = head1.next
        if head2: head2 = head2.next

    return dummy.next

Output:

5 -> 7 -> 9

In the provided code snippet, the add_linked_lists function takes the heads of two linked lists as arguments and returns the head of a new linked list representing the sum. A dummy head is used to simplify edge cases, and a ‘carry’ variable handles cases where the sum exceeds 9.

Method 2: Recursive Approach

The recursive approach takes advantage of the call stack to handle the addition of each node’s value. As the recursive calls return, the sum is calculated and new nodes are created. This method can be elegant but may incur added space complexity due to the call stack.

Here’s an example:

# Assume ListNode is defined as in Method 1

def add_linked_lists_recursive(head1, head2, carry=0):
    if not head1 and not head2 and not carry:
        return None
    
    val1, val2 = head1.value if head1 else 0, head2.value if head2 else 0
    carry, out = divmod(val1 + val2 + carry, 10)
    
    node = ListNode(out)
    node.next = add_linked_lists_recursive(
        head1.next if head1 else None, 
        head2.next if head2 else None, 
        carry)
    
    return node

Output:

5 -> 7 -> 9

The add_linked_lists_recursive function computes the sum at each corresponding position. If both input nodes are null and there’s no carry, it returns None, signifying the end of recursion. Otherwise, a new ListNode is created with the output value and the function is called recursively.

Method 3: Using Stack

Utilizing stacks can also be an effective approach. Both linked lists are traversed in full to populate two separate stacks. Popping items from the stack will give the nodes in reverse order, making it easy to handle carries from the sum calculation.

Here’s an example:

# Assume ListNode is defined as in Method 1

def add_linked_lists_stack(head1, head2):
    stack1, stack2 = [], []
    
    while head1:
        stack1.append(head1.value)
        head1 = head1.next
    while head2:
        stack2.append(head2.value)
        head2 = head2.next
    
    carry = 0
    prev = None
    while stack1 or stack2 or carry:
        val1 = stack1.pop() if stack1 else 0
        val2 = stack2.pop() if stack2 else 0
        carry, out = divmod(val1 + val2 + carry, 10)
        
        node = ListNode(out)
        node.next = prev
        prev = node
    
    return node

Output:

5 -> 7 -> 9

This code example uses two stacks to manage the linked list values in reverse order. By popping elements off the stack, the function creates a new linked list in the forward direction, correctly handling the addition and carry.

Method 4: Convert to Numbers and Rebuild

Another approach is to convert each linked list into its numerical representation, perform the addition, and then rebuild the linked list from this sum. This tends to be a simpler, though less efficient, method as it does not scale well with very long lists.

Here’s an example:

# Assume ListNode is defined as in Method 1

def linked_list_to_int(head):
    num = 0
    while head:
        num = num * 10 + head.value
        head = head.next
    return num

def int_to_linked_list(num):
    if num == 0: return ListNode(0)
    prev = None
    while num:
        num, value = divmod(num, 10)
        node = ListNode(value)
        node.next = prev
        prev = node
    return prev

def add_linked_lists_convert(head1, head2):
    num1 = linked_list_to_int(head1)
    num2 = linked_list_to_int(head2)
    total = num1 + num2
    return int_to_linked_list(total)

Output:

5 -> 7 -> 9

The code provided converts the linked lists to integers, adds them, and then converts the result back to a linked list. This method is intuitive and quite literal in how it approaches the problem of adding two numbers represented by linked lists.

Bonus One-Liner Method 5: Utilize Python Generator Expressions

This last method is a more Pythonic way, which involves generator expressions and the zip_longest utility from the itertools module. It’s a shorter and more elegant solution, suitable for cases when the lists are of different lengths.

Here’s an example:

from itertools import zip_longest

# Assume ListNode is defined as in Method 1

def add_linked_lists_zip(head1, head2):
    dummy = ListNode()
    tail = dummy
    carry = 0

    # Function to handle None values in lists of different lengths
    def value_or_zero(node):
        return node.value if node else 0
    
    for node1, node2 in zip_longest(head1, head2, fillvalue=None):
        carry, out = divmod(value_or_zero(node1) + value_or_zero(node2) + carry, 10)
        tail.next = ListNode(out)
        tail = tail.next
    
    if carry:
        tail.next = ListNode(carry)
    
    return dummy.next

Output:

5 -> 7 -> 9

The one-liner method elegantly iterates over both lists simultaneously using zip_longest and performs the addition. It is concise and handles carries and different list lengths with ease.

Summary/Discussion

  • Method 1: Iterative Approach. This method is straightforward and memory-efficient. It may not be as intuitive as the recursive approach but is typically faster due to not incurring the overhead of recursive function calls.
  • Method 2: Recursive Approach. Recursive code can be more readable and easier to maintain, though it may lead to stack overflow in languages that do not optimize tail recursion. Not recommended for very long lists.
  • Method 3: Using Stack. Stack-based solutions are excellent for reversal operations but have an additional space complexity overhead and may not be as straightforward to understand or implement as iterative solutions.
  • Method 4: Convert to Numbers and Rebuild. This approach is simple, but not efficient for large lists due to the risk of overflow and the O(n) complexity for list to integer and back conversions.
  • Method 5: Utilize Python Generator Expressions. The one-liner Pythonic approach is elegant and concise, especially suitable when the lists’ lengths differ, though it may be less intuitive for those not familiar with generator expressions and itertools.