每天一道算法题（java数据结构与算法)——＞两个链表的第一个公共节点

每天一道算法题（java数据结构与算法)——＞两个链表的第一个公共节点

题目

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

如下面的两个链表：

在节点 c1 开始相交。

题解1：（蛮方法）

在第1个链表中顺序遍历每个结点，每遍历到一个结点时，在2个链表中顺序遍历每一个结点（即嵌套循环）

代码实现

public class Solution {

    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
         // 外层循环，遍历第一个链表，每遍历一个结点，内层循环会遍历一遍第二个链表
        while (headA != null) {
            // 声明一个新节点，初始化为第二个链表头结点
            ListNode nB = headB;
           
            while (nB != null) {
                if (headA == nB) {
                    return nB;
                }
                nB = nB.next;
            }
            headA = headA.next;
        }
        return null;
    }
}

结点类

public class ListNode {

    T val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(T val) {
        this.val = val;
    }

    public ListNode(T val, ListNode next) {
        this.next = next;
    }
}

测试代码

public class Test {

    @org.junit.Test
    public void test1() {
        ListNode head1 = new ListNode<>("a1");
        ListNode one = new ListNode<>("a2");
        ListNode two = new ListNode<>("c1");
        ListNode three = new ListNode<>("c2");
        ListNode four = new ListNode<>("c3");
        head1.next = one;
        one.next = two;
        two.next = three;
        three.next = four;

        ListNode head2 = new ListNode<>("b1");
        ListNode first = new ListNode<>("b2");
        ListNode second = new ListNode<>("b3");
        head2.next = first;
        first.next = second;
        second.next = two;

        ListNode intersectionNode = Solution.getIntersectionNode1(head1, head2);
        System.out.println("两链表中的重合结点的值: " + intersectionNode.val);
    }
} 

复杂度分析

假设两链表长度为n，m

时间复杂度：嵌套遍历两个链表，则时间复杂度为O(nm);

空间复杂度：只声明了一个新结点，则空间复杂度为O(1)；

题解2：（栈方法）

思路分析

若两个链表存在公共结点，那么从第一个重合结点开始，往后所以结点都是重合的，因此可以从两个链表尾部开始遍历比较它们的结点，即最后一个相等结点就是第一个重合结点

由于链表只能从头结点开始遍历，而我们要的是从尾结点开始，因此可以使用栈来存放链表结点（先进后出）。在遍历链表时把结点压入栈，最先进的是头结点最后出，最晚进的是尾结点最先出。

1. 定义两个栈，存放两个链表结点
2. 遍历两个链表，遍历过程中把结点压入栈
3. 声明一个新结点，初始为null
4. 用一个循环依次把两个栈的栈顶元素d出并赋值给新结点，循环终结条件为两个栈为空且栈顶元素相等
5. 当循环终终止时，新结点存放的是最后一次循环栈d出的结点，此结点就是两链表第一个重合结点

实现代码

public class Solution {

    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    	// 声明两个栈，存放两个链表的结点
        Stack