- 1、题目描述:
- 2、题目链接:
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=188&tqId=37538&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&tab=answerKey
-3、 设计思想:
详细操作流程看下图:
-4、视频讲解链接B站视频讲解
-5、代码:
c++版本:
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here stack<int> s1,s2;//用来存储两个链表的数据 while (head1) {//将head1的元素放入栈1 s1.push(head1->val); head1 = head1->next; } while (head2) {//将head2的元素放入栈2 s2.push(head2 -> val); head2 = head2->next; } int cnt = 0;//如果两个值的加和>10,就会产生进位,这个用来存储进位 ListNode *res = nullptr; while (!s1.empty() || !s2.empty()) { int x1 = s1.empty() ? 0 : s1.top(); int x2 = s2.empty() ? 0 : s2.top(); if (!s1.empty()) s1.pop(); if (!s2.empty()) s2.pop(); int sum = x1 + x2 + cnt;//当前这一位的总和 cnt = sum / 10;//查看当前加和是否有进位 ///进行当前节点的插入 ListNode* tempNode = new ListNode(sum % 10); tempNode->next = res; res = tempNode; } ///最后一位的时候还得判断当时是否有进位如果存在进位就得在插入一个元素 if(cnt > 0){ ListNode* tempNode = new ListNode(cnt); tempNode->next = res; res = tempNode; } return res; } };
Java版本:
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { // write code here Stack<Integer> s1 = new Stack();//用来存储两个链表的数据 Stack<Integer> s2 = new Stack(); while (head1 != null) {//将head1的元素放入栈1 s1.push(head1.val); head1 = head1.next; } while (head2 != null) { //将head2的元素放入栈2 s2.push(head2.val); head2 = head2.next; } ListNode res = null; // 用于返回的链表 int cnt = 0; //如果两个值的加和>10,就会产生进位,这个用来存储进位 while (!s1.empty() || !s2.empty()) { // 从两个栈中各取一位 int x1 = s1.isEmpty() ? 0 : s1.pop(); int x2 = s2.isEmpty() ? 0 : s2.pop(); int sum = x1 + x2 + cnt;//当前这一位的总和 cnt = sum / 10;//查看当前加和是否有进位 ///进行当前节点的插入 ListNode tempNode = new ListNode(sum % 10); tempNode.next = res; res = tempNode; } if(cnt > 0){ ListNode tempNode = new ListNode(cnt); tempNode.next = res; res = tempNode; } return res; } }
Python版本:
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head1 ListNode类 # @param head2 ListNode类 # @return ListNode类 # class Solution: def addInList(self , head1 , head2 ): # write code here s1,s2 = [],[]#用来存储两个链表的数据 while head1:#将head1的元素放入栈1 s1.append(head1.val) head1 = head1.next while head2:#将head2的元素放入栈2 s2.append(head2.val) head2 = head2.next res = None cnt = 0#如果两个值的加和>10,就会产生进位,这个用来存储进位 while s1 or s2: x1 = 0 if not s1 else s1.pop() x2 = 0 if not s2 else s2.pop() sum = x1 + x2 + cnt#当前这一位的总和 cnt = sum // 10#查看当前加和是否有进位 #进行当前节点的插入 tempNode = ListNode(sum % 10) tempNode.next = res res = tempNode #最后一位的时候还得判断当时是否有进位如果存在进位就得在插入一个元素 if cnt: tempNode = ListNode(cnt) tempNode.next = res res = tempNode return res
JavaScript版本:
/* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ function addInList( head1 , head2 ) { // write code here let s1 = [];//用来存储两个链表的数据 let s2 = []; let res = null;// 用于返回的链表 let cnt = 0;//如果两个值的加和>10,就会产生进位,这个用来存储进位 while(head1){//将head1的元素放入栈1 s1.push(head1.val); head1 = head1.next; } while(head2){//将head2的元素放入栈2 s2.push(head2.val); head2 = head2.next; } while (s1.length || s2.length) {// 从两个栈中各取一位 let x1 = (s1.length ? s1.pop() : 0); let x2 = (s2.length ? s2.pop() : 0); let sum = x1 + x2 + cnt;//当前这一位的总和 cnt = Math.floor(sum / 10);//查看当前加和是否有进位 ///进行当前节点的插入 let tempNode = new ListNode(sum % 10); tempNode.next = res; res = tempNode; } if(cnt){ let tempNode = new ListNode(cnt); tempNode.next = res; res = tempNode; } return res; } module.exports = { addInList : addInList };