题目链接
思路1
先测量两个链表的长度,记录差值k=abs(n1 - n2)
,然后让短的链表先走k
步,这样就能保证剩下的长度是一样的,再同步遍历即可。
代码1
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA;
ListNode *p2 = headB;
int n1 = 0;
int n2 = 0;
// 分别测算两个链表的长度及其差值
while(p1){
p1 = p1->next;
++n1;
}
while(p2){
p2 = p2->next;
++n2;
}
int k = abs(n1 - n2);
p1 = headA;
p2 = headB;
// 总是让p1指向较长的那个链表
if(n1 < n2){
swap(p1, p2);
}
// 让较长的那个链表先走k步
while(k--){
p1 = p1->next;
}
// 再同步遍历
while(p1 && p2){
if(p1 == p2){
break;
}
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
思路2
根据题目意思 如果两个链表相交,那么相交点之后的长度是相同的
我们需要做的事情是,让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 为此,我们必须消除两个链表的长度差。
- 指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
- 如果 pa 到了末尾,则 pa = headB 继续遍历;如果 pb 到了末尾,则 pb = headA 继续遍历
- 比较长的链表指针指向较短链表head时,长度差就消除了
- 如此,只需要将最短链表遍历两次即可找到位置
可以理解成两个人速度一致, 走过的路程一致。那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话,那么这段路上俩人肯定是肩并肩手牵手的。
代码2
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return headA;
}
ListNode pa = headA;
ListNode pb = headB;
while(pa != pb){
pa = pa == null ? headB : pa.next;
pb = pb == null ? headA : pb.next;
}
return pa;
}
}
标签:p2,p1,ListNode,链表,headB,headA,160,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17021149.html