# Python Backtracking Solution

• Even for this question backtracking is not a easy way to solve it. But it still a way to solve this question and indeed it beat 50%.

#### First thing

we need to simplify question to add two linkedlist with same length.
this would be easy to do

``````        def add(l1,l2):
if not l1:
return (None,0)
else:
tmp = ListNode((l1.val + l2.val + carry)%10)
tmp.next = node
return [tmp,(l1.val + l2.val + carry)/10]
``````

#### Second thing

So now we all need to do is to add two linkedlist!
let say if we have two ls
`1 -> 2 -> 3` + `1 -> 2 -> 3` then all we need to is to call `add` function
since they have same length

BUT, if there it is two list we different length, we need to process so it works with this methos:
lets say we have :
`1 -> 2 -> 3 -> 4 -> 5` + `2 -> 1`
first we should break long list into two part
`P1` : `1 -> 2 -> 3`
`P2` : `4 -> 5`

By doing this, there is a part we can call `add` to calculate , which is

`2 -> 1`+ `4 -> 5` return `6 -> 6`

Now the only thing left is `P1` : `1 -> 2 -> 3`
So we can just link them together with `1 -> 2 -> 3->` (link) `6 -> 6`

Ha! we get the answer, but the real truggle is we have some data like

`1 -> 2 -> 3 -> 8 -> 8` + `2 -> 1`
So the same method will not work due to `8 -> 8` + `2 -> 1` will have a carry

What we have to do is to use the idea of back tracking , so the alg is

``````node,val = backtracking(` 2 -> 3 -> 8 -> 8`,` 2 -> 1`)
return carry = (node.val) + val/10
``````

Another struggle is find out which is one long list except find the length of two list.

``````class Solution(object):
if not l1:
return (None,0)
else:
tmp = ListNode((l1.val + l2.val + carry)%10)
tmp.next = node
return [tmp,(l1.val + l2.val + carry)/10]

####break long list into two part
h1,h2 = l1,l2
p1,p2 = None,None
s = ListNode(0)
while h1 and h2:
h1 = h1.next
h2 = h2.next
if h1:
s.next = l1
tmp = l1
while h1.next:
h1 = h1.next
tmp = tmp.next
p1 = tmp.next
tmp.next = None
p2 = l2
elif h2:
s.next = l2
tmp = l2
while h2.next:
h2 = h2.next
tmp = tmp.next
p1 = tmp.next
tmp.next = None
p2 = l1
if not p1:
p1,p2 = l1,l2
print "p1",p1
print "p2",p2
print s
###end of break long list into two part ///////

###put two list back to one and return it
def foo(ls):
if not ls.next:
ls.next = node
car =  (ls.val + c) /10
ls.val = (ls.val + c) %10
return car
tmp = ls
c = foo(tmp.next)
print "!" , ls , c
car = (ls.val + c)/10
ls.val = (ls.val + c) %10
return car
c = foo(s)
if not s:
return s.next
return s
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.