两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路

1. 假设两个链表的第一个公共结点为c。
2. 链表1可以表示为a+c，链表2可以表示为b+c。
3. 可以通过a+c+b+c = b+c+a+c来快速求出c的值，若没有公共结点，那c便是null。

4. 可以根据下图，简单理解下这个过程。

   
   
   

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
}

有疑问加站长微信联系（非本文作者）