环保公司网站建设,wordpress media,新泰高品质网站建设,互联网保险中介平台今天再写一道算法题#xff08;这两周都写算法题有点摆烂#xff09;
题目
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。
图示两个链表在节点 c1 开始相交#xff1…今天再写一道算法题这两周都写算法题有点摆烂
题目
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 注意
如果两个链表没有交点返回 null.在返回结果后两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度且仅用 O(1) 内存。
题目链接剑指 Offer 52. 两个链表的第一个公共节点
分析
如果你像我一样上来就怀疑这题为什么没有交叉链表的话那你的数据结构需要恶补下了。
这是链表的定义
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/对于单链表来说每个结点只会有1个后继但可以有很多个前驱。因此这两个链表只要有一处公共结点后面所有的结点就都是公共的。
此题的解法为双指针法
分别从两个链表的头指针开始向下同步遍历遍历完本链表后从对方链表的头指针开始每次比较遍历到的结点直到遍历的结点为公共结点或者返回null代表没遍历到。
双指针法的正确性证明可以参考 LeetCode 官方的证明
代码
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA nullptr || headB nullptr) {return nullptr;}ListNode *pA headA, *pB headB;while (pA ! pB) {pA pA nullptr ? headB : pA-next;pB pB nullptr ? headA : pB-next;}return pA;}
};
