怎么样做公司网站,大连公司地址,做公司点评的网站,网站为契机建设校园数字化链接#xff1a;
剑指 Offer 52. 两个链表的第一个公共节点
题意#xff1a;
如题
解#xff1a;
非常有趣的双指针 首先我们不管他们是否有公共段啊#xff0c;我们要知道一个指针从A出发走到A结尾#xff0c;再从B出发走到B结尾#xff0c;和从B出发最终到A结尾是…链接
剑指 Offer 52. 两个链表的第一个公共节点
题意
如题
解
非常有趣的双指针 首先我们不管他们是否有公共段啊我们要知道一个指针从A出发走到A结尾再从B出发走到B结尾和从B出发最终到A结尾是一样的距离那么我们先将最后面的N个排除N取两个链表最短长度-1 那么当Red指针到RedEnd位置Blue指针到BlueEnd的时候两个指针走过的距离是一样的也就是接下来两个指针同步指向倒数第K个节点由于公共段最多包含最后N1个节点BlueEnd和RedEnd就是倒数第N1个节点在此完成同步接下来判断两个指针是否指向同一个节点即可
我这边使用变量zt标记两个指针是否移动到了另一个链表如果都移动到了另一个链表还走到了结尾那就没有公共段
实际代码
#includeiostream
using namespace std;
struct ListNode
{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{ListNode *AheadA,*BheadB;if(headAnullptr||headBnullptr) return nullptr;int zt0; while(headA!headB||zt0){headAheadA-next;headBheadB-next;if(headAheadBzt!0) break;if(headAnullptr){headAB;zt;}if(headBnullptr){headBA;zt;}}return headA;
}
int main()
{}限制
如果两个链表没有交点返回 null.在返回结果后两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度且仅用 O(1) 内存。
