2023每日刷题(四十一)
Leetcode—160.相交链表
算法思想
两个链表的节点之和是相等的
如果两个链表相交,那么相交点之后的长度是相同的
我们需要做的事情是,让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。为此,我们必须消除两个链表的长度差
指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
如果 pA 到了末尾,则 pA = headB 继续遍历
如果 pB 到了末尾,则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时,长度差就消除了
如此,只需要将最短链表遍历两次即可找到位置
实现代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if(headA == NULL || headB == NULL) {return NULL;}struct ListNode* pa, *pb;pa = headA, pb = headB;while(pa != pb) {pa = pa == NULL ? headB: pa->next;pb = pb == NULL ? headA: pb->next;}return pa;
}
运行结果
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!