【leetcode】日积月累--面试题 02.07. 链表相交(DayDayUp 16)

简介: 链表相交一、题目二、代码及思路题目来源: 力扣官方题库等 级 : 简 单

一、题目


给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null。


图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不 存 在 环


注意,函数返回结果后,链表必须 保持其原始结构 。


1


微信图片_20211230111955.png


输入: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 个节点。


2


微信图片_20211230112154.png


输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1


输出:Intersected at ‘2’


解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。


从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。


在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。


3


微信图片_20211230112248.png


输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2


输出:null


解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。


由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。


这两个链表不相交,因此返回 null 。


提示:


  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点,intersectVal 为 0
  • 如果 listA 和 listB 有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]

二、代码及思路


思路:


先遍历两个链表得出两个链表长度,求出长度差为temp,然后让长的链表先走temp个节点,然后两个链表再逐个节点比较。相等则为有环输出值,如果没有相等的输出null


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while(curA != null){
            lenA++;
            curA = curA.next;
        }
        while(curB != null){
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        if(lenA >= lenB){
            int temp = lenA - lenB;
            while(temp-- != 0){
                curA = curA.next;
            }
        }else{
            int temp = lenB - lenA;
            while(temp-- != 0){
                curB = curB.next;
            }
        }
        while(curA != null && curB != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
相关文章
|
10天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
23 1
|
17天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
41 0
Leetcode第21题(合并两个有序链表)
|
17天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
13 0
LeetCode第二十四题(两两交换链表中的节点)
|
17天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
14天前
|
存储 算法 安全
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
|
17天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
39 0
|
17天前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
17 0
|
17天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
13 0
|
17天前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0
|
17天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
27 0