How can you find the sum of two linked lists representing numbers?

Arrays Linked Lists Questions Medium



46 Short 80 Medium 67 Long Answer Questions Question Index

How can you find the sum of two linked lists representing numbers?

To find the sum of two linked lists representing numbers, we can follow the below steps:

1. Initialize a dummy node and two pointers, one for each linked list.
2. Traverse both linked lists simultaneously, starting from the head nodes.
3. Keep track of the carry value initially set to 0.
4. At each step, add the corresponding values from both linked lists along with the carry value.
5. If the sum is greater than 9, update the carry value to 1 and take the modulo of the sum.
6. Create a new node with the value of the sum modulo 10 and attach it to the result linked list.
7. Move the pointers of both linked lists to their next nodes.
8. Repeat steps 4-7 until both linked lists are traversed completely.
9. If there is still a carry value remaining after traversing both linked lists, create a new node with the carry value and attach it to the result linked list.
10. Return the head of the result linked list.

Here is a Python implementation of the above algorithm:


```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def addTwoNumbers(l1, l2):
dummy = ListNode()
curr = dummy
carry = 0

while l1 or l2:
sum_val = carry

if l1:
sum_val += l1.val
l1 = l1.next
if l2:
sum_val += l2.val
l2 = l2.next

carry = sum_val // 10
curr.next = ListNode(sum_val % 10)
curr = curr.next

if carry:
curr.next = ListNode(carry)

return dummy.next
```

This algorithm has a time complexity of O(max(m, n)), where m and n are the lengths of the two linked lists.