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

问题陈述

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

如下面的两个链表**：**

在结点c1开始相交。

思路分析

分析一：

先得到A，B链的长度，若A长，则A先走A-B个长度；若B长，则B先走B-A个长度。然后一起走，直到两者相等，返回当前结点。

代码实现：

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 sulotion{
    public ListNode getIntersection(ListNode headA,ListNode headB){
        int lengthA=getLength(headA),lengthB=getLength(headB);
        ListNode first=headA,second=headB;
        if(lengthA>lengthB){
            for(int i=0;i<lengthA-lengthB;i++){
                first=first.next;
            }
        }else{
            for(int i=0;i<lengthB-lengthA;i++){
                second=second.next;
            }
        }
        if(first!=second){
            first=first.next;
            second=second.next;
        }
        return first;
    }
    public int getLength(ListNode temp){
        int length=0;
        for(ListNode node=temp;node!=null;node=node.next,length++);//学习此类循环
        return length;
    }
}

分析二：

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，两个结点就实现了同步，最后若相等，即是公共节点。

代码实现：

1
2
3
4
5
6
7
8
9
10
public class solution{
    public ListNode getIntersection(ListNode headA,ListNode headB){
        ListNode first=headA,second=headB;
        while(first!=second){
            first=first!=null? first.next:headB;
            second=second!=null? second.next:headA;
        }
        return first;
    }
}