算法:两个链表的第一个公共结点

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

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

输入两个链表，找出它们的第一个公共结点。

（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

分析

设定两个指针分别从list1和list2开始.

list1当到达链表1结尾时, 继续从链表2开始; list2同理;

最后:

• 长度相同时

  • 有公共结点，第一次就遍历到；
  • 没有公共结点，走到尾部NULL相遇，返回NULL

• 长度不同时

  • 有公共结点，第一遍差值就出来了，第二遍一起到公共结点
  • 没有公共，一起到结尾NULL

  ---

代码

public class Solution {
    public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        ListNode list1 = head1, list2 = head2;
        while (list1 != list2) {
            list1 = list1 == null ? head2 : list1.next;
            list2 = list2 == null ? head1 : list2.next;
        }
        return list1;
    }
}