逐日算法-链表（2.两数相加、24.两两交换链表中的节点、143.重排链表）
一.两数相加1.1题目描述
https://i-blog.csdnimg.cn/direct/3af59db8be1544928e1cf1eb4e3b0341.png
1.2题解思绪
https://i-blog.csdnimg.cn/direct/7775b952ec5a40fdb6e58238f098322b.png
定义两个指针l1,l2依次遍历两个链表，用变量add存储l1加l2的值，将add的个位数取出来充当新节点的值，然后将add的个位数删去，即add /=10，循环此操作。
重点分析：
1.跟归并排序中合并两个有序数组类似，当两个链表并不是一样长，此中一个链表并没有遍历完！！！
2.当两个链表都遍历完之后，如果add的值为1，则必要再增加一个节点，它的值为1.
1.3.题解代码
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int add = 0;
ListNode* newhead = new ListNode(-1);//创建虚拟头结点
ListNode* cur = newhead;
while(l1 && l2)
{
add += l1->val + l2->val;
ListNode* tmp = new ListNode(add%10);//将个位存进去
add /= 10;
cur->next = tmp;
l1 = l1->next;
l2 = l2->next;
cur = cur->next;
}
while(l1)
{
add += l1->val;
ListNode* tmp = new ListNode(add%10);
add /= 10;
cur->next = tmp;
l1 = l1->next;
cur = cur->next;
}
while(l2)
{
add += l2->val;
ListNode* tmp = new ListNode(add%10);
add /= 10;
cur->next = tmp;
l2 = l2->next;
cur = cur->next;
}
//判断边界情况
if(add == 1)
{
ListNode* tmp = new ListNode(1);
cur->next = tmp;
cur = cur->next;
}
return newhead->next;
}
}; 二.两两交换链表中的节点
2.1题目描述
https://i-blog.csdnimg.cn/direct/93082a30712e45c1969d1821bdbed15d.png
2.2题解思绪
https://i-blog.csdnimg.cn/direct/566abdae1e5d427cb0d987dfc144e80d.png
起首添加假造头结点，遍历这个链表，定义四个指针，prev,cur,next,nnext，模仿实现两个相邻链表翻转，然后更新prev,cur,next,nnext，循环此操作
重点分析：
1.当给的链表为空大概只有一个数据时，直接返回。
2.循环结束条件，当是偶数个数字时，cur!=nullptr，当是奇数个数字时，next != nullptr。
2.3题解代码
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode* newhead = new ListNode(-1);//虚拟头节点
newhead->next = head;
ListNode* prev = newhead,*cur = prev->next,*next = cur->next,*nnext = next->next;
while(cur && next)
{
prev->next = next;
next->next = cur;
cur->next = nnext;
prev = cur;
cur = nnext;
if(cur )next = cur->next;
if(next) nnext = next->next;
}
return newhead->next;
}
}; 三.重排链表
3.1题目描述
https://i-blog.csdnimg.cn/direct/a8b7379a847c418e981ee594f98d9aef.png
3.2题解思绪
1.找到链表的中央节点(快慢双指针)
2.将第二个链表逆序（头插法）
注意区分开curnext与cur->next，tmpnext与tmp->next
https://i-blog.csdnimg.cn/direct/afe9ca471f4048de8e835290514cf151.png
3.合并两个链表
注意必要把第一个链表的最后一个节点的next置空
https://i-blog.csdnimg.cn/direct/2f3e325d833f46c4a4467019b35b2172.png
3.3题解代码
class Solution {
public:
void reorderList(ListNode* head) {
if(!head->next || !head->next->next) return;
ListNode* newhead = new ListNode(-1);//添加虚拟头结点
//找到链表的中间节点(快慢双指针)
ListNode* q1 = head,*q2 = head;
while( q2->next && q2->next->next)
{
q1 = q1->next;
q2 = q2->next->next;
}
//反转q1后面的节点(头插法)
ListNode* tmp = new ListNode(-2);
ListNode* cur = q1->next,*curnext = cur->next,*tmpnext = tmp->next;
while(cur)
{
cout<<cur->val;
//头插
tmp->next = cur;
cur->next = tmpnext;
//更新指针
cur = curnext;
if(cur) curnext = cur->next;
tmpnext = tmp->next;
}
//合并两个链表
q1->next = nullptr;//注意！！！
ListNode* cur1 = head,*cur2 = tmp->next;
cur = newhead;
while(cur1 || cur2)
{
if(cur1)
{
cur->next = cur1;
cur1 = cur1->next;
cur = cur->next;
cur->next = nullptr;
}
if(cur2)
{
cur->next = cur2;
cur2 = cur2->next;
cur = cur->next;
cur->next = nullptr;
}
}
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]