【leetcode100-022】【链表/双指针】相交链表
2023-12-27 21:05:26
【题干】
给你两个单链表的头节点?headA
?和?headB
?,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回?null
?。
图示两个链表在节点?c1
?开始相交:
题目数据?保证?整个链式结构中不存在环。
注意,函数返回结果后,链表必须?保持其原始结构?。
【思路】
复试前写过这题,今天又碰上了,心情belike:
琢磨了很久终于想起来了,是那个很浪漫的链表相交。
- 首先,不难想到,如果有相交节点,那么对两个链表各自来说,该节点距离链表尾的距离肯定是相同的;
- 然后自然会想到,先统计一下节点数量,然后长的先走几步,接着两个指针一起走之类的,太常规了就不写一遍代码了;
- 虽然A和B不一定等长,但是,如果让两个指针都把A+B(B+A)走一遍,当它们都进入各自的第二条链时,距离末尾的长度就一定相等啦!
【题解】
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A = headA, *B = headB;
while (A != B) {
A = A != nullptr ? A->next : headB;
B = B != nullptr ? B->next : headA;
}
return A;
}
};
文章来源:https://blog.csdn.net/weixin_63059689/article/details/135251196
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!