写个算法还要各种查python语法…真可怜(⊙﹏⊙)b
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 contain a single digit.
Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
从左到右相加即可，注意进位的情况。
https://leetcode-cn.com/problems/add-two-numbers/
Python版本：
|
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ list1 = l1 list2 = l2 ansList = None rtList = ansList carry = 0 while list1!=None and list2!=None: temp = list1.val + list2.val + carry newNode = ListNode(temp % 10) carry = temp / 10 if(ansList == None): ansList = newNode rtList = ansList else: rtList.next = newNode rtList = rtList.next list1 = list1.next list2 = list2.next while list1: temp = list1.val + carry newNode = ListNode(temp % 10) carry = temp / 10 if(ansList == None): ansList = newNode rtList = ansList else: rtList.next = newNode rtList = rtList.next list1 = list1.next while list2: temp = list2.val + carry newNode = ListNode(temp % 10) carry = temp / 10 if(ansList == None): ansList = newNode rtList = ansList else: rtList.next = newNode rtList = rtList.next list2 = list2.next while carry: temp = carry newNode = ListNode(temp % 10) carry = temp / 10 if(ansList == None): ansList = newNode rtList = ansList else: rtList.next = newNode rtList = rtList.next return ansList |
新手python提示： 这里的与是 and ，不是 && …心疼(⊙﹏⊙)b
C++版本
|
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(l1 == nullptr) { return l2; } if(l2 == nullptr) { return l1; } ListNode* p1 = l1; ListNode* p2 = l2; ListNode* head = new ListNode(0); ListNode* ans = head; while(p1 != nullptr || p2 != nullptr) { if(ans->next == nullptr) { ans->next = new ListNode(0); } ans = ans->next; if(p1 != nullptr) { ans->val += p1->val; p1 = p1->next; } if(p2 != nullptr) { ans->val += p2->val; p2 = p2->next; } if(ans->val >= 10) { if(ans->next == nullptr) { ans->next = new ListNode(ans->val / 10); } else { ans->next->val += ans->val / 10; } ans->val = ans->val % 10; } } ans = head->next; delete head; return ans; } }; |
GO 版本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 37 38 39 40 41 |
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } ansList := &ListNode {0, nil} rtList := ansList for l1 != nil || l2 != nil { if ansList.Next == nil { ansList.Next = &ListNode {0, nil} } ansList = ansList.Next if l1 != nil { ansList.Val += l1.Val l1 = l1.Next } if l2 != nil { ansList.Val += l2.Val l2 = l2.Next } if ansList.Val >= 10 { if ansList.Next == nil { ansList.Next = &ListNode {0, nil} } ansList.Next.Val += ansList.Val / 10 ansList.Val = ansList.Val % 10 } } return rtList.Next } |
Go版本2：另外发现还可以递归来实现，代码短，但是耗费栈空间
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil && l2 == nil { return nil } if l1 == nil { return l2 } if l2 == nil { return l1 } count := l1.Val + l2.Val nextNode := addTwoNumbers(l1.Next, l2.Next) if count < 10 { return &ListNode{count, nextNode} } else { tmpNode := &ListNode {1, nil} return &ListNode {count - 10, addTwoNumbers(nextNode, tmpNode)} } } |
自行评判吧
【LeetCode】2. Add Two Numbers