Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q16

Q16 Add Two Numbers

Q

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Sample Input

image

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Input: l1 = [0], l2 = [0]
Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

1. My own Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        ls1, ls2, finls = [], [], [] #define empty list
        while l1:
            ls1.append(l1.val)
            l1 = l1.next
        while l2:
            ls2.append(l2.val)
            l2 = l2.next
        #finish conversion to the list
        
        ls1.reverse()
        ls2.reverse()
        #finish reversing
        
        lstsum = int(''.join(map(str, ls1))) + int(''.join(map(str, ls2)))
        #finish adding

        if lstsum == 0:
            finls.append(0)
        #exception - when both are 0

        while lstsum >= 1:
            left = lstsum%10
            finls.append(left)
            lstsum = lstsum//10
        #finish creating list consist of reversed number

        AnsNode = ListNode()
        head = AnsNode

        for val in finls:
            next = ListNode(val)
            AnsNode.next = next
            AnsNode = AnsNode.next

        return head.next

[Conversion to the List]
My solution is really simple. Just change linked list into the list, and then calculate. Therefore, my code is too much longer than the given one. Also, the run time is almost the worst… Execution time is the bottom 5%… ㅠㅠ Maybe no explanation is needed. My answer is really intuitive and easy to read.

2. Given Solution #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    #reversing linked-list
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node:
            next, node.next = node.next, prev
            prev, node = node, next

        return prev

    #divert linked-list to list
    def toList(self, node: ListNode) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list

    # List to linked-list
    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node

    #add to linked-list with the functions above
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))

        resultStr = int(''.join(str(e) for e in a)) + int(''.join(str(e) for e in b))

        return self.toReversedLinkedList(str(resultStr))

Almost same as mine. Simply divided my codes into many functions. Skip explanation.

3. Given Solution #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = head = ListNode(0)

        carry = 0
        while l1 or l2 or carry: 
            #until l1 or l2 exists, or when CARRY IN EXISTS so need to expand the digit.

            sum = 0 #initialize sum every loop

            #sum each digits(자릿수) if that node exists.
            if l1:
                sum+=l1.val
                l1 = l1.next
            if l2:
                sum+=l2.val
                l2 = l2.next

            #divmod returns the tuple of quotient and remainder.
            carry, val = divmod(sum+carry, 10) #from the previous digit, CI(carry in) can be 0 or 1
            head.next = ListNode(val)
            head = head.next

        return root.next

This is the solution using the “full-adder”. This derived from the concept that “How about adding each digit instead of converting linked-list to list.”

Overall Review

Not that hard problem. But with my solution, codes are so messed up because of many steps.

  1. Conversion from Linked-list to list
  2. Joining list elements to the single variable
  3. Make it integer type then add each other
  4. Convert the result to the linked-list

However, given sol #2 is very interesting. I just vaguely thought how about adding linked-list value itself by considering carry in, rather than following the complicated steps above. But I cannot realize my idea of embodying carry in. Using full-adder is the perfect solution to actualize the digit operation. There is no ending in learning CS…

참고