文章目录[隐藏]
这篇文章主要介绍了C++相交链表和反转链表,结合实例形式分析了C++相交链表和反转链表的原理、实现方法及相关注意事项,需要的朋友可以参考下
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路
简单来说，就是求两个链表交点节点的 指针。 这里同学们要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到焦点。
否则循环退出返回空指针。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* curA=headA; ListNode* curB=headB; int lenA=0; int lenB=0; while(curA!=nullptr){ // 求链表A的长度 lenA++; curA=curA->next; } while(curB!=nullptr){ // 求链表B的长度 lenB++; curB=curB->next; } //现在的curA,curB已经指向最后一个节点了，需要重新指向头结点 curA=headA; curB=headB; if(lenAnext; } while(lenB){ // 遍历curA 和 curB，遇到相同则直接返回 if(curA==curB) return curA; // return curA(val) 返回节点中的值，这个写法是错误的 直接return curA curA=curA->next; curB=curB->next; lenB--; } return nullptr; //没有交点则返回空 } };
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
双指针思路
首先判断链表是否为空，为空则返回nullptr。
接下来定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，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* reverseList(ListNode* head) { if(head==nullptr) //对空链表的判断 return nullptr; ListNode* per=nullptr; ListNode* cur=head; ListNode* temp; //建立一个指针 while(cur){ //没必要写 while(cur!=nullptr)，写了这个还要判断cur，会浪费时间，直接cur就可以 temp=cur->next; //保存cur的下一个节点 cur->next=per; //cur的下一个节点指向per,实现反转 per=cur; //cur=per;错误，是把cur的节点赋值给per cur=temp; //temp=cur;错误，是把temp(原来的cur->next)的节点赋值给cur } return per; } };
递归
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr)<em style="color:transparent">来源gao.dai.ma.com搞@代*码网</em> {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverse(ListNode* per,ListNode* cur){ //返回的是一个链表，其返回值是指针 if(cur==nullptr) //递归的终止条件 return per; ListNode* temp=cur->next; cur->next=per; return reverse(cur,temp); // 调用要写return } ListNode* reverseList(ListNode* head) { if(head==nullptr) //链表判空 return nullptr; return reverse(NULL,head); // 调用要写return } };
总结
以上就是C++相交链表和反转链表详解的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++相交链表和反转链表详解
转载请注明原文链接：C++相交链表和反转链表详解
