一、题目描述
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节
二、题解
方法一：计算链表长度
计算两个链表的长度，计算差值k,让长的链表先走k步，然后一起走
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA; ListNode pB = headB; int countA = 0; int countB = 0; while(pA!=null||pB!=null){ if(pA!=null){ countA++; pA = pA.next; } if(pB!=null){ countB++; pB = pB.next; } } int k = Math.abs(countA-countB); if(countA>countB){ pA = headA; pB = headB; }else{ pA = headB; pB = headA; } int count = 0; while(pA!=null&&pB!=null){ if(pA==pB) return pA; if(count>=k) pB = pB.next; pA = pA.next; count++; } return null; } }
方法二：
链表A的非公共字段长度为a,链表b的非公共字段长度为b,公共长度为c
a + c + b = b + c + a:即指针pa和指针pb走过相同的步数即可相遇
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode * pa = headA; ListNode * pb = headB; while(pa!=pb){ pa = pa==nullptr?headB:pa->next; pb = pb==nullptr?headA:pb->next; } return pa; } };
原文：https://www.cnblogs.com/ttzz/p/14369836.html