# 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

dummy = ListNode()
tail = dummy
carry = 0

carry, out = divmod(val1 + val2 + carry, 10)

tail.next = ListNode(out)
tail = tail.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

return None

carry, out = divmod(val1 + val2 + carry, 10)

node = ListNode(out)
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

stack1, stack2 = [], []

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

num = 0
num = num * 10 + head.value
return 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

total = num1 + num2
```

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

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

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.