0

We have two singly linked lists; hence, we can only traverse the structures in a single direction. Besides, we only have access to the head of the linked-list. The goal of the algorithm is to sum the figures of both linked lists and produce a third one with the answer. For instance, the linked list [6, 1, 7] + [2, 9, 5] should produce the result [9, 1, 2], given that 617 + 295 = 912.

For simplicity sake, we are going to asume that the original lists are the same length. Likewise, I'm not implementing the linked list data structure; instead, I'm using Python's built-in list but treating them as linked lists.

The solution I came up with is the following (Python code)

def sum_lists(l1, l2):
    lista = []
    carry = sum_forward(l1, l2, 0, lista)
    if carry > 0:
        lista.insert(0, carry) 
    return lista

def sum_forward(l1, l2, index, lista):
    if index == (len(l1)):        
        return 0
    total = l1[index] + l2[index] + sum_forward(l1, l2, index + 1, lista) #here
    #we have the iterative call.
    carry = total // 10
    value = total % 10    
    lista.insert(0, value) #This way we create a new head for the "surrogate     
    #linked-list" and append to it the resto of the values
    return carry

While this solution works fine, I've heard that any recursive solution can be turned into an iterative one. I've been banging may head for a couple of days but I'm unable to change this to a iterative solution.

I know this can be solved many ways; however, can this really be turned into a iterative solution?

Thanks guys!

I found the original problem in Gayle Laakmann Mcdowell's great book "Cracking the Coding Interview", in the subject of linked-lists.

KarloIsaac
  • 9
  • 3
  • step 1 is to reverse the lists – Matt Timmermans Apr 26 '19 at 15:55
  • @MattTimmermans Thanks. You're right. Actually, if the lists were inversed, the problem is much more easy to solve. Do you think it is possible to solve this problem without that previous step? What bugs me is the axiom "every recursive solution has a iterative counterpart" Is that even true? – KarloIsaac Apr 28 '19 at 20:32
  • @Prune I do not believe this question is a duplicate of the answer you are linking. I read thoroughly that answer and tried the proposed solutions. Specially, I tried to implement my own stack; nevertheless, I was unable to solve this problem iteratively given the constraints. As I see it, the complication is that you need to reach the last value of the list to start building the answer. Therefore, you cannot build a stack as the answer you're linking. Thanks. – KarloIsaac Apr 28 '19 at 20:43

1 Answers1

0

Here's one iterative solution:

l1 = [6,1,7]
l2 = [2,9,5]

def iterative_sum(l1, l2):
    maxlength = max(len(l1), len(l2))
    lsum = []
    sup = 0
    for i in range(maxlength):
        if l1 and l2:
            sup, num = divmod(l1.pop() + l2.pop() + sup, 10)
        elif l1 or l2:
            lleft = l1 or l2 # this assigns lleft to one of l1, l2 that still had element
            sup, num = divmod(lleft.pop() + sup, 10)
        lsum.append(num)
    return lsum[::-1]

iterative_sum(l1, l2)
# [9, 1, 2]
Rocky Li
  • 5,641
  • 2
  • 17
  • 33
  • This is not a linked list, but a normal list – Devesh Kumar Singh Apr 26 '19 at 15:40
  • replace the API then, use `curr = head; head=head.next` instead of `pop()`. The fundamental idea is the same. By the way, python `list` *are* singly linked list in implementation. – Rocky Li Apr 26 '19 at 16:28
  • Thanks @RockyLi. Your answer would be the right one if the lists were reversed (I've edited my question to make clearer that we only have access to the head of the lists). The `pop()` method returns and deletes the **last** element of the list; this is, **the tail** of the list. If we had access to the tail and we could traverse it backwards, this answer would approach the right one. Unfortunately, this is a singly linked list. Additionally this code fails with the input [6, 1, 7] and [2, 9, 5] (expected [1, 9, 1, 2]) – KarloIsaac Apr 29 '19 at 01:21