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:
node,carry = add(l1.next , l2.next)
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):
def addTwoNumbers(self, l1, l2):
###add number with same length
def add(l1,l2):
if not l1:
return (None,0)
else:
node,carry = add(l1.next , l2.next)
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:
node,c = add(p1,p2)
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
```