力扣160. 相交链表
Problem: 160. 相交链表题目描述
https://img-blog.csdnimg.cn/direct/b2ff324138ee4ffcb632432dabc49e37.pnghttps://img-blog.csdnimg.cn/direct/0b0bd62b53ef4f3f92339ff14f6af99f.pnghttps://img-blog.csdnimg.cn/direct/53f89e8231834e83ae834a7b24fa9127.pnghttps://img-blog.csdnimg.cn/direct/707c9f11f34e489a852277ea506d08dd.pnghttps://img-blog.csdnimg.cn/direct/b8392c4a62b3408f92a41092d8b791bd.pnghttps://img-blog.csdnimg.cn/direct/f4223f01d0584208ab4fad0e27502b5e.png
思路
用两个指针p1与p2分别指向headA与headB，当p1与p2不相当时，若p1遍历到链表A的尾部时再将p1指向headB继续遍历；若p2遍历到链表B的尾部时再将p2指向headA继续遍历；
复杂度
时间复杂度:
O ( m + n ) O(m + n) O(m+n)；其中 m m m是链表A的长度 n n n是链表B的长度
空间复杂度:
O ( 1 ) O(1) O(1)
Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
public class Solution {
/**
* Find intersecting nodes of intersecting linked lists
*
* @param headA The head node of linked list A
* @param headB The head node of linked list B
* @return ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
if (p1 == null) {
p1 = headB;
} else {
p1 = p1.next;
}
if (p2 == null) {
p2 = headA;
} else {
p2 = p2.next;
}
}
return p1;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]