AcWing 66. 两个链表的第一个公共结点

暴力做法，两层for循环

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
class Solution {public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {for(ListNode p = headA; p != null; p = p.next){for(ListNode q = headB; q != null; q = q.next){if(p == q){return p;}}}return null;}
}

双指针

（1）设链表A独有部分长a，链表B独有部分长b，公共部分长c，让两个指针分别从链表A和链表B头开始移动，若移动到末尾仍未相遇则移动到对方的链表头。
（2）若二者相交，则由 a+c+b=b+c+a。可知，两个指针必会在第二轮遍历时在公共结点相遇。
（3）若二者不相交，则二者同样必会在第二轮遍历的末尾同时为NULL，进而判断两链表不相交。
（4）最多只会执行两轮遍历，就能够得出结果。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
class Solution {public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {ListNode p = headA, q = headB;while(p != q){if(p == null){p = headA;}else{p = p.next;}if(q == null){q = headB;}else{q = q.next;}}return p;}
}