题目
思路
思路一 较简单,但是不美丽
- 分别求出两条链表的长度,求出其差值为 k
- 将p指向长链表的头节点,然后移动 k 步
- q 指向短链表的头节点
- p,q 同时后移,直到相遇或者为null 也就是不存在交集。
很巧妙的思路
链表A 长度为 a,
链表B 长度为 b,
二者公共长度为 c.
那么按照代码的移动方式,
p 从 A 出发要走 a+(b-c)
q 从 B 出发要走 b+(a-c)
如果存在相同的节点,那么最后相遇的位置就是第一个公共节点
如果不存在,最后二者都走到了 null,再返回,也恰好符合题意。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A=headA,B=headB;
while(A!=B){
A=A!=null?A.next:headB;
B=B!=null?B.next:headA;
}
return A;
}
}