IT评测·应用市场-qidao123.com技术社区

标题: 逐日算法-链表（2.两数相加、24.两两交换链表中的节点、143.重排链表） [打印本页]
作者: 大连全瓷种植牙齿制作中心    时间: 2025-4-16 06:20
标题: 逐日算法-链表（2.两数相加、24.两两交换链表中的节点、143.重排链表）
一.两数相加

1.1题目描述


1.2题解思绪


定义两个指针l1,l2依次遍历两个链表，用变量add存储l1加l2的值，将add的个位数取出来充当新节点的值，然后将add的个位数删去，即add /=10，循环此操作。
重点分析：
1.跟归并排序中合并两个有序数组类似，当两个链表并不是一样长，此中一个链表并没有遍历完！！！
2.当两个链表都遍历完之后，如果add的值为1，则必要再增加一个节点，它的值为1.
1.3.题解代码

  1. class Solution {
  2. public:
  3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  4.         int add = 0;
  5.         ListNode* newhead = new ListNode(-1);//创建虚拟头结点
  6.         ListNode* cur = newhead;
  7.         while(l1 && l2)
  8.         {
  9.             add += l1->val + l2->val;
  10.             ListNode* tmp = new ListNode(add%10);//将个位存进去
  11.             add /= 10;
  12.             cur->next = tmp;
  13.             l1 = l1->next;
  14.             l2 = l2->next;
  15.             cur = cur->next;
  16.         }
  17.         while(l1)
  18.         {
  19.             add += l1->val;
  20.             ListNode* tmp = new ListNode(add%10);
  21.             add /= 10;
  22.             cur->next = tmp;
  23.             l1 = l1->next;
  24.             cur = cur->next;
  25.         }
  26.         while(l2)
  27.         {
  28.             add += l2->val;
  29.             ListNode* tmp = new ListNode(add%10);
  30.             add /= 10;
  31.             cur->next = tmp;
  32.             l2 = l2->next;
  33.             cur = cur->next;
  34.         }
  35.         //判断边界情况
  36.         if(add == 1)
  37.         {
  38.             ListNode* tmp = new ListNode(1);
  39.             cur->next = tmp;
  40.             cur = cur->next;
  41.         }
  42.         return newhead->next;
  43.     }
  44. };
复制代码
二.两两交换链表中的节点

2.1题目描述


2.2题解思绪


起首添加假造头结点，遍历这个链表，定义四个指针，prev,cur,next,nnext，模仿实现两个相邻链表翻转，然后更新prev,cur,next,nnext，循环此操作
重点分析：
1.当给的链表为空大概只有一个数据时，直接返回。
2.循环结束条件，当是偶数个数字时，cur!=nullptr，当是奇数个数字时，next != nullptr。
2.3题解代码

  1. class Solution {
  2. public:
  3.     ListNode* swapPairs(ListNode* head) {
  4.         if(!head || !head->next) return head;
  5.         ListNode* newhead = new ListNode(-1);//虚拟头节点
  6.         newhead->next = head;
  7.         ListNode* prev = newhead,*cur = prev->next,*next = cur->next,*nnext = next->next;
  8.         while(cur && next)
  9.         {
  10.             prev->next = next;
  11.             next->next = cur;
  12.             cur->next = nnext;
  13.             prev = cur;
  14.             cur = nnext;
  15.             if(cur )next = cur->next;
  16.             if(next) nnext = next->next;
  17.         }
  18.         return newhead->next;
  19.     }
  20. };
复制代码
三.重排链表

3.1题目描述


3.2题解思绪

1.找到链表的中央节点(快慢双指针)
2.将第二个链表逆序（头插法）
注意区分开curnext与cur->next，tmpnext与tmp->next

3.合并两个链表
注意必要把第一个链表的最后一个节点的next置空

3.3题解代码

  1. class Solution {
  2. public:
  3.     void reorderList(ListNode* head) {
  4.         if(!head->next || !head->next->next) return;        
  5.         ListNode* newhead = new ListNode(-1);//添加虚拟头结点            
  6.         //找到链表的中间节点(快慢双指针)   
  7.         ListNode* q1 = head,*q2 = head;
  8.         while( q2->next && q2->next->next)
  9.         {
  10.             q1 = q1->next;
  11.             q2 = q2->next->next;
  12.         }
  13.         //反转q1后面的节点(头插法)
  14.         ListNode* tmp = new ListNode(-2);
  15.         ListNode* cur = q1->next,*curnext = cur->next,*tmpnext = tmp->next;
  16.         while(cur)
  17.         {
  18.             cout<<cur->val;
  19.             //头插
  20.             tmp->next = cur;
  21.             cur->next = tmpnext;
  22.             //更新指针
  23.             cur = curnext;
  24.             if(cur) curnext = cur->next;
  25.             tmpnext = tmp->next;
  26.         }
  28.         //合并两个链表
  29.         q1->next = nullptr;//注意！！！
  30.         ListNode* cur1 = head,*cur2 = tmp->next;
  31.         cur = newhead;
  32.         while(cur1 || cur2)
  33.         {
  34.             if(cur1)
  35.             {
  36.                 cur->next = cur1;
  37.                 cur1 = cur1->next;
  38.                 cur = cur->next;
  39.                 cur->next = nullptr;
  40.             }
  41.             if(cur2)
  42.             {
  43.                 cur->next = cur2;
  44.                 cur2 = cur2->next;
  45.                 cur = cur->next;
  46.                 cur->next = nullptr;
  47.             }
  48.         }
  49.     }
  50. };
复制代码





免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4