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

这题也太经典了,我也说倦了。

解法一:加法交换律法

A/B链表非公共部分为a/b,公关部分为c。
A:a+c+b
B:b+c+a
以上两者相等。
相遇时就是公共节点。
注意它们可能无交点的情况,所以等跑到null了之后再指向另一个链表头。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null) return null;
        ListNode p1=pHead1, p2=pHead2;
        while(p1!=p2){
            p1= (p1==null? pHead2:p1.next);
            p2= (p2==null? pHead1:p2.next);
        }
        return p1;
    }
}

解法二:快慢指针法

记录两个链表长度,允许长的那个先跑多出来的长度。
好无聊,代码略。