题目描述

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

解题思路

如果两个链表存在公共结点,那么它们从公共结点开始一直到链表的结尾都是一样的,因此我们只需要从链表的结尾开始,往前搜索,找到最后一个相同的结点即可。但是题目给出的单向链表,我们只能从前向后搜索,这时,我们就可以借助栈来完成。先把两个链表依次装到两个栈中,然后比较两个栈的栈顶结点是否相同,如果相同则出栈,如果不同,那最后相同的结点就是我们要的返回值。
还有一种方法,不需要借助栈。先找出2个链表的长度,然后让长的先走两个链表的长度差,然后再一起走,直到找到第一个公共结点。

参考代码

法1:Stack

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while(pHead1 != null){
            s1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2 != null){
            s2.push(pHead2);
            pHead2 = pHead2.next;
        }

        ListNode res = null;
        while(!s1.isEmpty() && !s2.isEmpty() && s1.peek() == s2.peek()){
            s1.pop();
            res = s2.pop();
        }
        return res;
    }
}

法2:

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)
            return null;
        int count1 = 1, count2 = 1;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1.next != null){
            p1 = p1.next;
            count1++;
        }
        while(p2.next != null){
            p2 = p2.next;
            count2++;
        }
        if(count1>count2){
            int dif = count1 - count2;
            while(dif != 0){
                pHead1 = pHead1.next;
                dif--;
            }
        }else{
            int dif = count2 - count1;
            while(dif != 0){
                pHead2 = pHead2.next;
                dif--;
            }
        }
        while(pHead1 != null && pHead2 != null){
            if(pHead1 == pHead2)
                return pHead1;
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}

互联网校招面试必备——Redis

Redis有哪些数据结构? 字符串String、字典Hash、列表List、集合Set、有序集合SortedSet。 如果你是Redis中高级用户,还需要加上下面几种数据结构HyperLogLog...

阅读全文

互联网校招面试必备——数据库

DDL(Data Definition Language)数据库定义语言 CREATE、ALTER、DROP、TRUNCATE、COMMENT、RENAME DML(Data Manipulation Language)数据操纵语言 SELECT、...

阅读全文

一文搞定BAT面试——Java 集合类

1. Iterator接口 Iterator接口,这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基...

阅读全文