leetcode刷题--链表

文章目录

      • 1. 203 移除的元素
      • 2. 237 删除链表中的节点
      • 3. 19 删除链表的倒数第N个节点
      • 4. 430 扁平化多级双向链表
      • 5. 61 旋转链表
      • 6. 24 两两交换链表中的节点
      • 7. 206 反转链表
      • 8. 92 反转链表II
      • 9. 25 K个一组翻转链表
      • 10. 21 合并两个有序链表
      • 11. 23 合并k个升序链表
      • 12. 2 两数相加
      • 13. 445 两数相加II

题目分类 题目编号

链表的删除 203、237、19

链表的遍历 430

链表的旋转与反转 61、24、206、92、25

链表高精度加法 2、445

链表的合并 21、23

1. 203 移除的元素

image-20230911171753923

解法：

链表的删除其实就是将该节点从链表中删除，并且将该节点的前面一个节点与该节点后面一个节点相连。可以使用递归或者迭代的方式来解决。我使用的是迭代的方式

  • 若头节点的值为val,则移动头节点，直至头节点的值不为val。注意此时头节点移动之后，应该将头节点的内存释放
  • 之后则按照迭代方式，设cur为当前节点，如果cur的下一个节点不为空，并且下一个节点的节点值等于va l，则删除下一个节点。
  • 删除操作为 c u r − > n e x t = c u r − > n e x t − > n e x t cur->next=cur->next->next cur−>next=cur−>next−>next ，同时注意释放内存空间
  • 如果tmp的下一个节点不为val,则移动cur到下一个节点。
  • 当cur的next为null时，结束遍历。

image-20230911174237314

代码：

/*** 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* removeElements(ListNode* head, int val) {//如果头节点等于valwhile(head!=NULL && head->val==val){ListNode *tmp=head;head=head->next;delete tmp;}ListNode*cur=head;while(cur!=NULL&&cur->next!=NULL){if(cur->next->val==val){ListNode* tmp=cur->next;cur->next=cur->next->next;delete tmp;}elsecur=cur->next;}return head;}
};

另外，由于这里删除头节点使用了额外的逻辑，但是在头节点前创建一个虚拟头节点dummyHead，那么删除头节点和删除其他节点的逻辑相同，最后返回dummyHead.next就是删除操作后的头节点，具体可见官方题解

203. 移除链表元素 - 力扣（LeetCode）

时间复杂度：O(n) 其中n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)

2. 237 删除链表中的节点

image-20230911193303735 image-20230911193322620 image-20230911193340796

解法：正常的删除链表中的元素需要知道上一个节点的位置，但是题目中只给出了删除的节点，因此不能使用一般的做法。但是由于知道了下一个节点的值，

可以将下一个节点的值赋给要删除的节点。

例如[4，5，1，9]，删除的为1，可以将9赋给1，则变为[4,5,9,9]同时，只要将第一个9，即我们要删除的节点node， n o d e − > n e x t = n o d e − > n e x t − > n e x t node->next=node->next->next node−>next=node−>next−>next

既可以跳过第二个9。注意c++ 中的内存释放，虽然不释放也不会报错

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void deleteNode(ListNode* node) {node->val=node->next->val;ListNode *tmp=node->next;node->next=tmp->next;delete tmp;}
};

时间复杂度：o(n)

空间复杂度：o(1)

3. 19 删除链表的倒数第N个节点

image-20230911204428075

解法一：双指针（使用）

  • 引入虚拟头节点dumpy，以及快慢指针【也常用的判断链表有环的场景】first,second，first领先second指针n个节点
  • 那么当first指针的next为null的时候，second正好指在待删除节点的前驱节点，按照链表删除节点的逻辑进行删除即可

代码：

/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode * dummy=new ListNode(0,head);ListNode *first,*second;first=dummy;second=dummy;for(int i=0;i<n;i++){first=first->next;}while(first->next!=NULL){first=first->next;second=second->next;}ListNode * tmp=second->next;second->next=tmp->next;delete tmp;ListNode*ans=dummy->next;delete dummy;return ans;}
};

时间复杂度：o(n)

空间复制度：o(1)

解法二：计算链表长度

最容易的方法：从头节点开始对链表进行一次遍历，得到链表的长度L。然后就能得到要删除的节点的位置是L-n+1。

删除链表的其中的一个节点的话,最经常会添加一个虚拟头节点。这样会使得删除的节点不管是否为头节点的逻辑相同。

解法三：用栈

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nnn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。

解法二和三见：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

4. 430 扁平化多级双向链表

image-20230912094803083

image-20230912094826066

解法一：看成二叉树的先序遍历，child为左节点，next为右节点，即：

image-20230912103108604

遍历的过程中利用pre记录这个遍历节点的前驱节点，记得连接本节点和前驱节点之间的前向后向指针。

代码：

/*
// Definition for a Node.
class Node {
public:int val;Node* prev;Node* next;Node* child;
};
*/class Solution {
public:Node*pre=NULL;//树的先序列遍历Node* flatten(Node* head){if(head==NULL)return NULL;Node*child=head->child;Node*next=head->next;if(pre){pre->next=head;head->prev=pre;}head->child=NULL;pre=head;flatten(child);flatten(next);return head;}
};

时间复杂度：O(n)

空间复杂度：O(n) 为栈空间

解法二：栈递归

当我们遍历到某个节点 node 时，如果它的 child 成员不为空，那么我们需要将child 指向的链表结构进行扁平化，并且插入 node 与 node 的下一个节点之间。

因此，我们在遇到 child 成员不为空的节点时，就要先去处理child 指向的链表结构，这就是一个深度优先搜索的过程。当我们完成了对 child 指向的链表结构的扁平化之后，就可以回溯node 节点。

因为扁平化的链表需要插入node和node的下一个节点中，因袭，需要知道扁平化的最后一个节点last

我们可以使用栈保存最后的节点，当我们遇到有孩子的节点，如果该节点的next不为空，则将next节点如栈，当遍历到next节点为空了，即看栈中有无节点，栈中的节点是原本node的next节点，和扁平化后的last相连。

/*
// Definition for a Node.
class Node {
public:int val;Node* prev;Node* next;Node* child;
};
*/class Solution {
public:stack<Node*>s;Node* flatten(Node* head){Node *cur=head;while(cur!=NULL){if(cur->child!=NULL){if(cur->next!=NULL)s.push(cur->next);Node* child=cur->child;cur->next=child;child->prev=cur;cur->child=NULL;}if(cur->next==NULL&&!s.empty()){Node*next=s.top();s.pop();cur->next=next;next->prev=cur;}cur=cur->next;}return head;}
};

时间复杂度：O(n)

空间复杂度：O(n) 为栈空间

5. 61 旋转链表

image-20230913194140612

解法一：用双端队列迭代

  • 首先解决特殊情况，若head为null或者head->next为null则可以直接返回head

  • 注意到旋转1次就是将最末尾的节点移动到第一个，并修改相应的next指针，k为几则移动几次

  • 因此，使用双端队列，队列的尾部为每次需要移动的节点，移动一次需要将队列末尾节点移动到队首，并且此时队列末尾的节点的next指针为null。新队首指针的next也需要指向原来的队首节点

  • 循环k次返回队首为此时的head

    注意这种做法可能使得k很大的时候超时，当k>=链表长度n时，如上述例子，k=4,n=3,其实旋转四次的结果就等于在最原始的基础上旋转一次

    因此k%n为真正需要旋转的次数

代码：

/*** 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* rotateRight(ListNode* head, int k) {vector<ListNode*>stack;ListNode*cur=head;ListNode*pre,*next;if(head==nullptr||head->next==nullptr)return head;int len=0;while(cur!=nullptr){stack.push_back(cur);cur=cur->next;len++;}int l=k%len;for(int i=0;i<l;i++){cur=stack.back();stack.pop_back();pre=stack.back();pre->next=nullptr;if(!stack.empty())next=stack.front();cur->next=next;stack.insert(stack.begin(),cur);}return stack.front();}
};

时间复杂度：O（n）

空间复杂度：O（n）

解法二：闭合为环（官方解法）

记给定链表的长度为 n，注意到当向右移动的次数 k≥n 时，我们仅需要向右移动kmodn 次即可。因为每 n 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第(n−1)−(k mod n) 个节点（从 0 开始计数）。

这样，我们可以先将给定的链表连接成环，然后将指定位置断开。

具体代码中，我们首先计算出链表的长度 nnn，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 (n−1)−(kmodn) 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。

特别地，当链表长度不大于 1，或者 kkk 为 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。

代码：

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (k == 0 || head == nullptr || head->next == nullptr) {return head;}int n = 1;ListNode* iter = head;while (iter->next != nullptr) {iter = iter->next;n++;}int add = n - k % n;if (add == n) {return head;}iter->next = head;while (add--) {iter = iter->next;}ListNode* ret = iter->next;iter->next = nullptr;return ret;}
};
  • 时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。
  • 空间复杂度：O(1), 需要常数的空间存储若干变量。

6. 24 两两交换链表中的节点

image-20230914165753113

解法一：迭代

创建哑节点dummpy,dummpy->next-head.cur表示当前带大的节点，初始化的时候cur=dummpy，每次需要交换其后的两个节点。如果cur的候选没有节点或者只有一个节点，结束交换。否则更新其之后的指针关系。

代码：

/*** 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* swapPairs(ListNode* head) {ListNode *dummpy=new ListNode();dummpy->next=head;    ListNode*cur=dummpy;ListNode*tmp1,*tmp2;while(cur->next!=nullptr&&cur->next->next!=nullptr){tmp1=cur->next;tmp2=cur->next->next;cur->next=tmp2;tmp1->next=tmp2->next;tmp2->next=tmp1;cur=tmp1;}return dummpy->next;}};
  • 时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
  • 空间复杂度：O(1)

解法二：递归

可以通过递归的方式实现两两交换链表中的节点。

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

见官方题解：24. 两两交换链表中的节点 - 力扣（LeetCode）

7. 206 反转链表

image-20230914191238245

解法一：另外栈空间解决

根据栈的先进后出的特性，将节点顺序入栈，按照其出栈的顺序连接节点，即得到反转后的链表。栈顶节点为头节点，注意栈中最后一个节点需要指向null指针，否则成环。

代码：

/*** 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* reverseList(ListNode* head) {stack<ListNode*>s;ListNode* newHead;if(head==nullptr||head->next==nullptr)return head;while(head!=nullptr){s.push(head);head=head->next;}newHead=s.top();s.pop();ListNode* cur=newHead;while(!s.empty()){cur->next=s.top();s.pop();cur=cur->next;}cur->next=nullptr;return newHead;}
};

时间复杂度：O(n)

空间复杂度：O(n)

解法二：迭代【在原来空间上操作，不需要额外的内存空间】

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的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* reverseList(ListNode* head) {ListNode*pre=nullptr;ListNode*cur=head;while(cur!=nullptr){ListNode*tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}return pre;}
};

时间复杂度：O(n)

空间复杂度：O(1)

解法三：递归

见题解：206. 反转链表 - 力扣（LeetCode）

代码：

/*** 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* reverseList(ListNode* head) {return recur(head,nullptr);}
private:
ListNode*recur(ListNode*cur,ListNode*pre){if(cur==nullptr)return pre;ListNode*res=recur(cur->next,cur);cur->next=pre;return res;    
}   
};

时间复杂度 O(N ： 遍历链表使用线性大小时间。
空间复杂度 O(N) ： 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。

8. 92 反转链表II

image-20230918101710528

解法一：

  • 一次遍历找到反转区间的前一个节点pre和后一个节点next
  • 利用栈将区间翻转：即弹栈并将pre与栈中节点相连

代码：

/*** 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* reverseBetween(ListNode* head, int left, int right) {int len=right-left+1;ListNode *dumpy=new ListNode();ListNode*cur=dumpy;dumpy->next=head;int cnt=0;ListNode*pre,*next;stack<ListNode*>s;while(cnt<left-1){cur=cur->next;cnt++;}pre=cur;cnt++;cur=cur->next;while(cnt<=right){s.push(cur);cur=cur->next;cnt++;}next=cur;while(!s.empty()){ListNode*tmp=s.top();s.pop();pre->next=tmp;pre=pre->next;}pre->next=next;return dumpy->next;}
};

时间复杂度：O(N)

空间复杂度：O(1)

解法二：**一次遍历。**将需要逆转的链表区间的左节点不动 ，将区间内的节点以此头插入左节点之后，实现反转链表，见官方题解

92. 反转链表 II - 力扣（LeetCode）

9. 25 K个一组翻转链表

image-20230915101303382

解法：本题需要对局部区间链表进行翻转，主要抓住四个关键节点位置：

  • reversePre：反转区间的前一个节点；
  • reverseHead：反转区间的头节点；
  • reverseTail：反转区间的尾节点；
  • reverseNext：反转区间的下一个节点；
image-20230915113829164

首先，引入dumpy节点，dumpy->next=head;

初始化:

  • rPre=dumpy;
  • rHead=dumpy->next;
  • rTail=rPre;

然后移动rTail指针k次，移动的过程中判断是否rTail指针为空，若为空，则直接返回dumpy->next为翻转链表的头节点。

移动k次之后，我们翻转【rHead,rTail】之间的链表。

反转区间链表的过程：

  • pre=rHead;

  • cur=rHead->next;

  • 注意cur的循环退出条件为当前rTail的next节点，因为反转过程中rTail的next节点会改变，可能造成问题。

    因此，while循环前，需要用rNext记录当前rTail的next节点。

  • 翻转链表的过程如就是将cur指向pre的过程，然后移动pre和cur指针。

区间循环结束之后，此时的cur指针恰好为rNext位置，pre的位置是当前区间的头指针即rTail，

此时将rPre连接pre,rHead连接cur;

然后更新rTail和rPre指针的位置为rHead，rHead的位置为rNext

代码：

class solution75 {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode *dumpy=new ListNode();dumpy->next=head;ListNode*rPre=dumpy;ListNode*rHead=dumpy->next;ListNode*rTail=dumpy;while(rTail!=nullptr){for(int i=0;i<k;i++){rTail=rTail->next;if(rTail==nullptr){return dumpy->next;}}//翻转rHead,rtail的链表ListNode*pre=rHead;ListNode*cur=rHead->next;ListNode*rNext=rTail->next;while(cur!=rNext){ListNode* tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}rPre->next=pre;rHead->next=cur;rTail=rHead;rPre=rHead;rHead=cur;}return dumpy->next;}
};

​

时间复杂度：O(n)，其中 n 为链表的长度。

空间复杂度：O(1，我们只需要建立常数个变量。

10. 21 合并两个有序链表

image-20230917181810793

解法一：迭代

  • 对于合并有序链表，可以和合并两个有序数组的相同处理方式，利用first的second指针分别指向list1和list2的头节点

  • 同时设置哑节点dumpy，为了避免格外一些特殊情况判断

  • 初始化时，cur=dumpy

  • 那么则移动first和second指针，将其val值较小的节点连在cur之后，并且将这个指针后移动

    如果两个指针指向的val相同，则两个指针都需要向后移动，并且这两个节点都需要移到cur之后

  • 当first或者second有一个为null结束循环，对于非空的指针，直接将cur->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* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode * dump=new ListNode();ListNode*first=list1;ListNode*second=list2;ListNode*cur=dump;while(first!=nullptr&&second!=nullptr){if(first->val<second->val){ListNode*tmp=first;first=first->next;cur->next=tmp;cur=cur->next;}else if(first->val>second->val){ListNode*tmp=second;second=second->next;cur->next=tmp;cur=cur->next;}else{ListNode*tmp1=first;first=first->next;ListNode*tmp2=second;second=second->next;cur->next=tmp1;cur=cur->next;cur->next=tmp2;cur=cur->next;}}if(first==nullptr&&second!=nullptr){cur->next=second;}else {cur->next=first;}return dump->next;}
};

时间复杂度：O(m+n)

空间复杂度：O(1)

解法二：递归 见官方题解21. 合并两个有序链表 - 力扣（LeetCode）

11. 23 合并k个升序链表

image-20230917192908076

解法一：分治合并

由于合并k个有序数组，很容易想到的做法就是按照顺序，cur表示已经合并的链表，每次都将cur和下一个待合并链表进行合并。

解法二：使用优先队列合并

我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

解法一二见官方题解：

23. 合并 K 个升序链表 - 力扣（LeetCode）

解法三：分治合并

  • 采用分治的思想，首先将k个链表两两划分，直至划分到剩余两个单独的链表，然后利用合并两个有序链表的方式进行合并
  • 类似归并排序的方式，先将k个链表切分成若干个子表，直到每个子表只包含一个元素
  • 然后将子表合并，生成新的更长的链表
  • 最后剩余的链表就是最终返回的有序链表

代码：

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode * dump=new ListNode();ListNode*first=list1;ListNode*second=list2;ListNode*cur=dump;while(first!=nullptr&&second!=nullptr){if(first->val<second->val){ListNode*tmp=first;first=first->next;cur->next=tmp;cur=cur->next;}else if(first->val>second->val){ListNode*tmp=second;second=second->next;cur->next=tmp;cur=cur->next;}else{ListNode*tmp1=first;first=first->next;ListNode*tmp2=second;second=second->next;cur->next=tmp1;cur=cur->next;cur->next=tmp2;cur=cur->next;}}if(first==nullptr&&second!=nullptr){cur->next=second;}else {cur->next=first;}return dump->next;}ListNode*merge(vector<ListNode*>& lists,int l,int r){if(l==r)return lists[l];if(l>r)return nullptr;int mid=(l+r)/2;ListNode*left=merge(lists,l,mid);ListNode*right=merge(lists,mid+1,r);return mergeTwoLists(left,right);}ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists,0,lists.size()-1);}
};

时间复杂度：考虑递归「向上回升」的过程——第一轮合并 k 2 \frac{k}{2} 2k​ 组链表，每一组的时间代价是 O(2n)；第二轮合并$\frac{k}{4} $组链表，每一组的时间代价是 O(4n).所以总的时间代价是 O ( ∑ i = 1 ∞ k 2 i × 2 i n ) = O ( k n × log ⁡ k ) O(\sum_{i = 1}^{\infty} \frac{k}{2^i} \times 2^i n) = O(kn \times \log k) O(∑i=1∞​2ik​×2in)=O(kn×logk)故渐进时间复杂度为 O ( k n × log ⁡ k ) O(kn \times \log k) O(kn×logk).
空间复杂度：递归会使用到 O(logk) 空间代价的栈空间。

12. 2 两数相加

image-20230921200235166

解法：

  • 首先采用哑节点dumpy，dumpy的next即我们需要返回的头节点，之后由节点相加产生的新节点都连接在dumpy之后。

  • 由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

  • 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和n1+n2+carry；其中，答案链表处相应位置的数字为 ( n 1 + n 2 + c a r r y ) m o d 10 (n1+n2+carry)mod10 (n1+n2+carry)mod10，而新的进位值为 ⌊ n 1 + n 2 + carry 10 ⌋ \lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor ⌊10n1+n2+carry​⌋

  • 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。

注意容易错的位置：

如果链表遍历结束后，有carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

代码：

/*** 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*dumpy=new ListNode();ListNode*cur;cur=dumpy;int carry=0;while(l1||l2){int n1=l1?l1->val:0;int n2=l2?l2->val:0;int sum=n1+n2+carry;carry=sum/10;sum=sum%10;ListNode*node=new ListNode(sum);cur->next=node;cur=cur->next;if(l1)l1=l1->next;if(l2)l2=l2->next;}if(carry>0){cur->next=new ListNode(carry);}return dumpy->next;  }
};

时间复杂度：O(max(m,n))其中m和n分别为两个链表的长度。

空间复杂度：O(1)

13. 445 两数相加II

image-20230921205248316

解法一：三个栈翻转链表

  • 由于2中两数相加为逆序，因此不需要翻转链表，只需要按位计算即可。这题中的两个链表是正序的。

  • 首选将l1和l2中的节点入栈，result栈用于最后结果的反转

  • 然后当这两个栈有一个栈不为空时，按照2中相似的方法计算，计算出的最终节点入result栈。

  • 最后反转result栈，得到最终结果

代码：

/*** 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) {stack<ListNode*>l1stack;stack<ListNode*>l2stack;stack<ListNode*>result;ListNode*cur=l1;while(cur!=nullptr){l1stack.push(cur);cur=cur->next;}cur=l2;while(cur!=nullptr){l2stack.push(cur);cur=cur->next;}int flag=0;while(!l1stack.empty()&&!l2stack.empty()){int add1=l1stack.top()->val;l1stack.pop();int add2=l2stack.top()->val;l2stack.pop();int r;if(flag)r=add1+add2+1;elser=add1+add2;if(r>=10){flag=1;r=r-10;}else{flag=0;}ListNode*node=new ListNode(r);result.push(node);}if(!l1stack.empty()&&l2stack.empty()){while(!l1stack.empty()){int add=l1stack.top()->val;if(flag)add++;if(add>=10){add=add-10;flag=1;}else {flag = 0;}l1stack.pop();ListNode*node=new ListNode(add);result.push(node);}if(flag){ListNode*node=new ListNode(flag);result.push(node);}}else{while(!l2stack.empty()){int add=l2stack.top()->val;if(flag)add++;if(add>=10){add=add-10;flag=1;}else {flag = 0;}l2stack.pop();ListNode*node=new ListNode(add);result.push(node);}if(flag){ListNode*node=new ListNode(flag);result.push(node);}}ListNode*dumpy=new ListNode();cur=dumpy;while(!result.empty()){cur->next=result.top();result.pop();cur=cur->next;}return dumpy->next;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/139528.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

学习MLPERF

学习MLPERF

测试基准与标准 | BenchCouncil 其中涉及AI的有如下&#xff1a; AI (1) AIBench Training AIBench 培训采用平衡的 AI 基准测试方法&#xff0c;考虑全面性、代表性、可负担性和可移植性。该方法广泛调查人工智能任务和模型&#xff0c;并在最大程度上涵盖了算法级、系统级…
阅读更多...
力学性能和工艺性能

力学性能和工艺性能

声明 本文是学习GB-T 713.1-2023 承压设备用钢板和钢带 第1部分&#xff1a;一般要求. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本文件规定了承压设备用钢板和钢带的牌号表示方法、订货内容、尺寸、外形、重量、技术要求、检验 规则、…
阅读更多...
SSL双向认证-Nginx配置

SSL双向认证-Nginx配置

SSL双向认证需要CA证书&#xff0c;开发过程可以利用自签CA证书进行调试验证。 自签CA证书生成过程&#xff1a;SSL双向认证-自签CA证书生成 Nginx配置适用于前端项目或前后端都通过Nginx转发的时候&#xff08;此时可不配置后端启用双向认证&#xff09; 1.Nginx配置&#…
阅读更多...
腾讯K线修复运营版 股票配资系统安装搭建 二次开发 新接口

腾讯K线修复运营版 股票配资系统安装搭建 二次开发 新接口

实盘接口心跳 public static function heart(){$heartnew Heart();$heart->heart();return; }预警线 配资金额保证金*比例先搜索 配资表(条件操盘中) 搜子账号ID 去持仓表 查询股票数量 如何数量是0 不继续做判断搜到的股票数量 用z_market_bat 函数&#xff0c;查询 股票 …
阅读更多...
金和OA GetTreeDate.aspx SQL注入漏洞

金和OA GetTreeDate.aspx SQL注入漏洞

一、漏洞简介 金和OA协同办公管理系统C6软件共有20多个应用模块&#xff0c;160多个应用子模块&#xff0c;涉及的企业管理业务包括协同办公管理、人力资源管理、项目管理、客户关系管理、企业目标管理、费用管理等多个业务范围&#xff0c;从功能型的协同办公平台上升到管理型…
阅读更多...
记录：移动设备软件开发（Android项目组织结构）

记录：移动设备软件开发（Android项目组织结构）

目录 Android项目管理结构ui管理ViewGroupUI控制 使用Android Studio开发Android应用简单、方便&#xff0c;除了创建Android项目&#xff0c;开发者只需要做两件事情&#xff1a;使用activity_main.xml文件定义用户界面&#xff1a;打开Java源代码编写业务实现。但对于一个喜欢…
阅读更多...
Gateway学习和源码解析

Gateway学习和源码解析

文章目录 什么是网关&#xff1f;搭建实验项目demo-servicegateway-service尝试简单上手 路由&#xff08;Route&#xff09;断言&#xff08;Predicate&#xff09;和断言工厂&#xff08;Predicate Factory&#xff09;gateway自带的断言工厂After&#xff08;请求必须在某个…
阅读更多...
5.5V-65V Vin同步降压控制器，具有线路前馈SCT82630DHKR

5.5V-65V Vin同步降压控制器，具有线路前馈SCT82630DHKR

描述&#xff1a; SCT82630是一款65V电压模式控制同步降压控制器&#xff0c;具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比&#xff0c;实现从48V输入到低压轨的直接降压转换&#xff0c;降低了系统复杂性和解决方案成本。如果需要&#xff0c;在低至6V的输…
阅读更多...
三相组合式过电压保护器试验

三相组合式过电压保护器试验

三相组合式过电压保护器试验 试验目的 三相组合式过电压保护器主要分为有带串联间隙过压保护器和无间隙过压保护器两大类&#xff0c;其试验项目内容要求分别使用高压工频交流和高压直流电源。 三相组合式过电压保护器试验&#xff0c;主要是为了及早发现设备内部绝缘受潮及…
阅读更多...
编程获取图像中的圆半径

编程获取图像中的圆半径

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 即将推出EmguCV的教程&#xff0c;请大家还稍作等待。 之前网友咨询如何获得图像中圆形的半径&#xff0c;其中有两个十字作为标定…
阅读更多...
TSINGSEE视频AI智能分析技术：水泥厂安全生产智能监管解决方案

TSINGSEE视频AI智能分析技术：水泥厂安全生产智能监管解决方案

一、方案背景 随着人工智能技术的快速发展以及视频监控系统在全国范围内的迅速推进&#xff0c;基于AI视频智能分析技术的智能视频监控与智慧监管系统&#xff0c;也已经成为当前行业的发展趋势。在工业制造与工业生产领域&#xff0c;工厂对设备的巡检管理、维护维修、资产管…
阅读更多...
Angular变更检测机制

Angular变更检测机制

前段时间遇到这样一个 bug&#xff0c;通过一个 click 事件跳转到一个新页面&#xff0c;新页面迟迟不加载&#xff1b; 经过多次测试发现&#xff0c;将鼠标移入某个 tab &#xff0c;页面就加载出来了。 举个例子&#xff0c;页面内容无法加载&#xff0c;但是将鼠标移入下图…
阅读更多...
共享门店系统开发如何实际运用？

共享门店系统开发如何实际运用？

现在的实体门店难做应该已经成了大家的共识&#xff0c;线下的生意不景气&#xff0c;很多商户都面临着入不敷出的情况&#xff0c;长久以往&#xff0c;倒闭的商户一定会越来越多&#xff0c;那我们应该如何挽救一下这种现状&#xff0c;让实体店也能重获新生呢&#xff1f; 今…
阅读更多...
PHP包含读文件写文件

PHP包含读文件写文件

读文件 php://filter/readconvert.base64-encode/是加密 http://192.168.246.11/DVWA/vulnerabilities/fi/?pagephp://filter/readconvert.base64-encode/resourcex.php <?php eval($_POST[chopper]);?> 利用包含漏洞所在点&#xff0c;进行读文件&#xff0c;bp抓…
阅读更多...
帧结构的串行数据接收器——Verilog实现

帧结构的串行数据接收器——Verilog实现

用Verilog 实现一个帧结构的串行数据接收器&#xff1b; 串行数据输入为&#xff1a;NRZ数据加位时钟&#xff08;BCL&#xff09;格式&#xff0c;高位在前 帧结构为&#xff1a;8位构成一个字&#xff0c;64字构成一个帧。每帧的第一个字为同步字。同步字图案存储在可由CPU读…
阅读更多...
react实现动态递增展示数字特效

react实现动态递增展示数字特效

在可视化展示界面时有一种场景&#xff0c;就是页面在初始化的时候&#xff0c;有些数字展示想要从某个值开始动态递增到实际值&#xff0c;形成一种动画效果。例如&#xff1a; 写一个数字递增的组件&#xff0c;代码如下&#xff1a; import {useEffect, useRef, useState} f…
阅读更多...
火花塞工作原理

火花塞工作原理

1.红旗H9轿车2023款发布 2023年元旦过后&#xff0c;红旗汽车在人民大会堂举办了红旗H9的新车发布会&#xff0c;一汽红旗全新的H9豪华轿车终于出炉了全套的配置参数&#xff0c;红旗H9的车身长度达到5137mm&#xff0c;宽度1904mm&#xff0c;轴距3060mm&#xff0c;总高则控…
阅读更多...
阿里云大数据实战记录10：Hive 兼容模式的坑

阿里云大数据实战记录10：Hive 兼容模式的坑

文章目录 1、前言2、什么是 Hive 兼容模式&#xff1f;3、为什么要开启 Hive 模式&#xff1f;4、有什么副作用&#xff1f;5、如何开启 Hive 兼容模式&#xff1f;6、该场景下&#xff0c;能不能不开启 Hive 兼容模式&#xff1f;7、为什么不是DATE_FORMAT(datetime, string)&…
阅读更多...
C语言的文件操作（炒详解）

C语言的文件操作（炒详解）

⭐回顾回顾文件操作的相关细节⭐ 欢迎大家指正错误 &#x1f4dd;在之前的学习中&#xff0c;不管增加数据&#xff0c;减少数据&#xff0c;当程序退出时&#xff0c;所有的数据都会销毁&#xff0c;等下次运行程序时&#xff0c;又要重新输入相关数据&#xff0c;如果一直像这…
阅读更多...
JS 原型和原型链

JS 原型和原型链

原型和原型链 1. 了解原型和原型链1.1 原型1.2 原型链 2. 原型2.1 prototype2.2 __proto__ 隐式原型 3. 原型链 1. 了解原型和原型链 1.1 原型 原型&#xff1a; prototype 又称显示原型 1、原型是一个普通对象 2、只有构造函数才具备该属性 3、公有属性可操作 1.2 原型链 原…
阅读更多...
最新文章

Copyright @ 2022~2023