当前位置：首页 > article >正文

LeetCode：面试题 02.07. 链表相交

article 2024/11/16 7:22:11

🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

题解目录

一、🌱[面试题 02.07. 链表相交](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/)
- 🌴解题
- - 1. 计算长度差
  - 2. 双栈

一、🌱面试题 02.07. 链表相交

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
来源：力扣（LeetCode）
难度：简单
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 10⁴
1 <= Node.val <= 10⁵
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

🌴解题

1. 计算长度差

链表相交，指的是两个链表后面一段是公共的，因此我们可以计算两个链表长度，以尾部对齐的方式从同一个位置开始遍历，看节点是不是相同的（不是值相等，NodeA==NodeB）。
就是计算两个链表长度之差 N，让长链表先走 N 步~
然后两个链表同步遍历。

code：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pointA = headA,pointB = headB;
        int lengthA=getListLength(headA);
        int lengthB=getListLength(headB);
        int diffn=0;
        if(lengthA>lengthB){
            diffn=lengthA-lengthB;
            while (diffn>0){
                pointA=pointA.next;
                diffn--;
            }
        }
        if(lengthA<lengthB){
            diffn=lengthB-lengthA;
            while (diffn>0){
                pointB=pointB.next;
                diffn--;
            }
        }        
        while (pointA!=pointB){
            pointA=pointA.next;
            pointB=pointB.next;
        }        
        return pointA;
    }

    private int getListLength(ListNode headA) {
        int len=0;
        while(headA!=null){
            len++;
            headA=headA.next;
        }
        return len;        
    }
}

在这里插入图片描述

2. 双栈

同样考虑到栈先进后出的性质，准备两个栈来存两个链表节点，依次出栈对比~
注意 ListA.peek()==ListB.peek() 的栈空相等的情况。

code：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)
            return null;
        Deque<ListNode> ListA=new LinkedList<>();
        Deque<ListNode> ListB=new LinkedList<>();
        ListNode ans=null;
        while (headA!=null){
            ListA.push(headA);
            headA=headA.next;
        }
        while (headB!=null){
            ListB.push(headB);
            headB=headB.next;
        }
        while (ListA.peek()==ListB.peek()){
            ans=ListA.pop();//保存最后一个相等的节点，交点
            ListB.pop();
            if(ListA.isEmpty()||ListB.isEmpty())
                break;
        }
        return ans;
    }
}