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