即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

两个链表的第一个公共结点(java版)

编程语言 ouyangyanlan 17℃ 0评论

【题目描述】输入两个链表,找出它们的第一个公共结点。

注:默认为单链表,且无环


【解题思路】


//1.两个单链表若存在公共结点,则从第一个公共结点开始,后面的结点都是公共的。


//2.比较两个链表的长度。设置两个指针,分别指向两个链表的头结点。较长的链表的指针先走|len1-len2|步。然后两个指针同时向后移动,两个指针相遇时,即为两个链表的第一个公共结点。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null || pHead2==null){
            return null;
        }
        int len1=0, len2=0, i=0;
        ListNode p1=pHead1, p2=pHead2;
        //计算链表1的长度
        while(p1.next!=null){
            p1 = p1.next;           
            len1++;
        }
        //计算链表2的长度
        while(p2.next!=null){
            p2 = p2.next;
            len2++;
        }
        p1=pHead1;
        p2=pHead2;
        if(len1>len2){
            while(ielse{
            while(iwhile(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

【解题思路2】走过你来时的路


//1. 设置两个指针,初始位置分别指向两个链表的头结点。


//2. 短链表的指针先走到尾结点,长链表的指针还未到达尾结点。然后,两个链表的长度差就自然的被两个指针的位置记录了下来。


//3. 将先到达尾结点的指针,移动到长链表的头结点位置。长链表指针到达尾部时,移动指针到锻炼表的头结点位置。同时向后走,两个指针必然相遇。


//4. 可能会出现的情况有:


a.两个链表指针长度相同且存在公共结点,则第一次遍历的过程中即可求出第一个公共结点。


b.两个链表指针长度不同且存在公共结点,则第一次遍历得到两个链表的长度差,第二次遍历即可求出第一个公共结点。


c.两个链表无公共结点,则最后返回null

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null || pHead2==null){
            return null;
        }
        ListNode p1=pHead1, p2=pHead2;
        while(p1!=p2){
            p1 = (p1==null ? pHead2 : p1.next);
            p2 = (p2==null ? pHead1 : p2.next);
        }
        return p1;
    }
}

【解题思路3】


//1.运用HashMap来存储链表1的节点。


//2.遍历链表2,判断当前节点是否作为key已经在map中出现。若有,则返回该节点。若无,则继续遍历,直到结束,返回null

import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        HashMap hashMap = new HashMap();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }
        return null;
    }
}

【解题思路4】


如果存在共同节点的话,那么从该节点,两个链表之后的元素都是相同的。也就是说两个链表从尾部往前到某个点,节点都是一样的。


//1. 设置两个指针,初始化位置分别指向两个链表的头结点。


//2. 遍历每个链表,使得指针分别指向各自的尾部。


//3. 从尾部同时向前移动,若相同的最后一个节点,即为第一个公共结点。


//4. 借助栈来实现单链表的逆向访问。

链接:https://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46
来源:牛客网

import java.util.Stack;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if (pHead1 == null || pHead2 == null) {
            return null;
        }
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();
        while (pHead1 != null) {
            stack1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            stack2.push(pHead2);
            pHead2 = pHead2.next;
        }
        ListNode commonListNode = null;
        while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek() ) {
            stack2.pop();
            commonListNode = stack1.pop();;
        }
        return commonListNode;
    }
}

转载请注明:CodingBlog » 两个链表的第一个公共结点(java版)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情