题目描述
输入两个链表,找出它们的第一个公共结点。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
思路
- 假设两个链表的第一个公共结点为c。
- 链表1可以表示为a+c,链表2可以表示为b+c。
- 可以通过a+c+b+c = b+c+a+c来快速求出c的值,若没有公共结点,那c便是null。
- 可以根据下图,简单理解下这个过程。
Java代码实现
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1 = pHead1; ListNode p2 = pHead2; while(p1 != p2){ p1 = (p1==null)?pHead2:p1.next; p2 = (p2==null)?pHead1:p2.next; } return p1; } }
Golang代码实现
func getIntersectionNode(headA, headB *ListNode) *ListNode { pA,pB := headA,headB for headA != headB { if headA == nil{ headA = pB }else { headA = headA.Next } if headB == nil{ headB = pA }else { headB = headB.Next } } return headB }