牛客题解-NC66两个链表的第一个公共节点

发表于 更新于 分类于 阅读次数：

题目

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

思路

分析

从两个链表的头节点出发，同时向后移动，当某一个链表的指针为空后，此时到了链表尾，指向另一个链表的头节点，这样，最终两个指针会在两个链表的同一相对位置。此时继续遍历就能找到第一个公共节点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
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 l1 = pHead1;
        ListNode l2 = pHead2;
        while(l1 != l2){
            l1 = l1.next;
            l2 = l2.next;
            if(l1 != l2){
                if(l1 == null) l1 = pHead2;
                if(l2 == null) l2 = pHead1;
            }
        }
        return l1;
    }
}