剑指offer——两个链表的第一个公共节点

时间:2022-10-25 11:01:22

剑指offer——两个链表的第一个公共节点

题目描述

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

我的未通过解法:空指针异常

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1=getLength(pHead1);
        int len2=getLength(pHead2);
        if(len1==0 || len2==0){
            return null;
        }
        //ListNode p=pHead1;
        while(len1-len2>0){
            pHead1=pHead1.next;
        }
        while(len1-len2<0){
            pHead2=pHead2.next;
        }
        while(pHead1!=pHead2){
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
        return pHead1;
    }
    public int getLength(ListNode pHead){
        //一定要注意,处理该函数时,不要直接处理头结点,否则到最后头结点会指向最后一个结点的下一个节点,即null。
        //即处理链表时注意复位!
        ListNode ln=pHead;
        int len=0;
        while(ln!=null){
            len++;
            ln=ln.next;
        }
        return len;
    }

}

错误原因:当两个链表长度不一样时,将长的链表先遍历长度差个元素时为改变长度,导致while循环不能终止!!!

改正解法

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1=getLength(pHead1);
        int len2=getLength(pHead2);
        if(len1==0 || len2==0){
            return null;
        }
        //ListNode p=pHead1;
        int num=len1-len2;
        while(num>0){
            pHead1=pHead1.next;
            num--;
        }
        while(num<0){
            pHead2=pHead2.next;
            num++;
        }
        while(pHead1!=pHead2){
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
        return pHead1;
    }
    public int getLength(ListNode pHead){
        //一定要注意,处理该函数时,不要直接处理头结点,否则到最后头结点会指向最后一个结点的下一个节点,即null。
        //即处理链表时注意复位!
        ListNode ln=pHead;
        int len=0;
        while(ln!=null){
            len++;
            ln=ln.next;
        }
        return len;
    }

}

注意点

一般情况下,对链表的操作,一般不要对链表头结点直接进行操作,可以新建一个结点,使其等于头结点,然后对新建的这个结点进行操作,这样,当之后再使用原链表时,可以很容易的早到头结点,然后进行相应的操作。

因此,改进之后的代码如下:

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1=getLength(pHead1);
        int len2=getLength(pHead2);
        if(len1==0 || len2==0){
            return null;
        }
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        int num=len1-len2;
        while(num>0){
            p1=p1.next;
            num--;
        }
        while(num<0){
            p2=p2.next;
            num++;
        }
        while(p1!=p2){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
    public int getLength(ListNode pHead){
        //一定要注意,处理该函数时,不要直接处理头结点,否则到最后头结点会指向最后一个结点的下一个节点,即null。
        //即处理链表时注意复位!
        ListNode ln=pHead;
        int len=0;
        while(ln!=null){
            len++;
            ln=ln.next;
        }
        return len;
    }

}

提升

利用hashMap的特性进行求解。

import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;


        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }

        return null;

    }
}

HashMap参考学习资料:Java中的Collections类