leetcode简单题之链表的两数相加 |
您所在的位置：网站首页 › java数字相加 › leetcode简单题之链表的两数相加 |
|
题目链接：力扣 我的思路：可以使用数组模拟，但是提交的时候内存会超限。使用内存不超限的方法，使用较长的那个链表来存储相加的结果。使用一个变量来存储相加的结果，看两个数相加时是否会产生进位，对两个链表进行遍历，逐步相加，如果在最后一位产生进位，我们则需要新开辟一个节点来存储相加后的进位，使用四个指针来解决这个问题，ptr1和ptr2来分别指向两个链表相加时的位置，ptr来指向较长的那个链表，K指向较长链表的最后一个位置，如果在最后一位相加时产生了进位，则K->next=新开辟的那个节点。 解题代码： /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *ptr1=l1; ListNode *ptr2=l2; int len1=0,len2=0; while(ptr1){ len1++; ptr1=ptr1->next; } while(ptr2){ len2++; ptr2=ptr2->next; } ListNode *head=len1>=len2?l1:l2;//找出长的那个链表的头结点 ListNode *ptr=head; ListNode *K=head; ptr1=l1,ptr2=l2; int temp=0; while(ptr1||ptr2||temp!=0){ int x=ptr1?ptr1->val:0; int y=ptr2?ptr2->val:0; int add=x+y+temp; if(add>=10){ if(ptr){ ptr->val=add%10; ptr=ptr->next; } } else{ if(ptr){ ptr->val=add; ptr=ptr->next; } else{ ListNode *temp=new ListNode(add%10);//最后产生进位时新开辟的节点 K->next=temp;//让它成为K的下一个节点 } } if(K->next){ K=K->next;//能使K指向链表的最后一个节点 } if(ptr1){ ptr1=ptr1->next; } if(ptr2){ ptr2=ptr2->next; } temp=add/10; } return head; } };时间复杂度: O(max(l1.length,l2.lenght)) 空间复杂度: O(1) |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |