剑指offer - 两个链表的第一个公共结点(Java实现)

题目链接：https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&&tqId=11189&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路：此题的意思是说，给你两个链表，让你找到这个链表的第一个公共结点，这里的第一个公共结点指的是，如果链表的当前结点相同，那么两个链表的后半部分将完全相同。此时我们就可以考虑这么一种情况：

  我们将两个字符串按照图示的内容拼接起来，如果存在第一个节点，那么在 len(pHead1) + len(pHead2) 次内我们一定可以找到这么一个公共结点，如果没有这样一个公共结点，那么两个指针最后最终均指向 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 p = pHead1, q = pHead2;
        while(p != q) {
            p = p.next;
            q = q.next;
            if(p != q) {//可能两个指针都指向了null
                if(p == null) p = pHead2;
                if(q == null) q = pHead1;
            }
        }
        return p;
    }
}

//题解区简单写法
/*
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 p = pHead1, q = pHead2;
        while(p != q) {
            p = p == null ? pHead2 : p.next;
            q = q == null ? pHead1 : q.next;
        }
        return p;
    }
}