找到两个链表的第一个公共节点

思路

• 两个相交的单链表，不可能是x型，只可能是Y型，因为相交处的节点只有一个next，只能保存一份地址，也就是说从相交的节点开始，后面每个节点都是同一个节点了
• 假设有两个链表A链表和B链表
• 先得到两个链表的长度lenA,lenB
• 如果lenA>lenB,那么先让A链表走lenA-lenB步，反之，让B链表走lenB-lenA步
• 遍历比较指向链表的两个引用(引用中存的是地址，==比较身份，也就是比较地址是否相同)，如果相等就返回这个引用指向的节点，遍历结束没找到就返回null​​​​​​

代码

public class Solution9 {
    public int getLength(ListNode head){
        int length=0;
        for(ListNode cur=head;cur!=null;cur=cur.next){
            length++;
        }
        return length;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1=getLength(headA);
        int len2=getLength(headB);
        ListNode curA=headA;
        ListNode curB=headB;
        if(len1>len2){
            int steps=len1-len2;
            for(int i=0;i<steps;i++){
                curA=curA.next;
            }
        }else{
            int steps=len2-len1;
            for(int i=0;i<steps;i++){
                curB=curB.next;
            }
        }
        while(curA!=null&&curB!=null){
            if(curA==curB){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
}

最后

以上就是粗心雨为你收集整理的找到两个链表的第一个公共节点的全部内容，希望文章能够帮你解决找到两个链表的第一个公共节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。