一、前言
每日算法坚持第四天，该专栏争取日日更新，加油
二、简介和示例
简介
LeetCode 面试题 02.07. 链表相交: 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
网络异常，图片无法展示
|
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
链表数据结构
public class ListNode { public int val; public ListNode next; public ListNode() { } public ListNode(int val) { this.val = val; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } } 复制代码
示例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 个节点。 复制代码
示例2
网络异常，图片无法展示
|
输入：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
网络异常，图片无法展示
|
输入：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]
三、解题
错误示范
注意: 这里求的是指针相同的情况下的交点, 而不是求相同的数值, 这个就很烦, 最开始读题没有读明白, 提交代码的时候还报错
网络异常，图片无法展示
|
错误代码展示
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 两个链表, 记录 headA和 headB的元素值 List<Integer> list1 = new ArrayList<>(); List<Integer> list2 = new ArrayList<>(); // 链表A和B, 题中有说不改变原先的链表 ListNode one = headA; ListNode two = headB; // 遍历获取链表的值 while(one != null){ list1.add(one.val); one = one.next; } while(two != null){ list2.add(two.val); two = two.next; } // 判断最短长度去循环 int size = list1.size() < list2.size() ? list1.size() : list2.size(); // 返回值链表 ListNode node = null; // 遍历循环 int j = 1; for (int i = size - 1 ; i >= 0; i--) { if (list1.get(i) != list2.get(list2.size() - j)){ if (i < size){ node = new ListNode(list1.get(i + 1)); } break; } j++; } return node; } 复制代码
思路分析
- 首先一定要注意, 我们要求的是同指针下的交点
- 因为题中要求不改变原链表结构
- 首先, 我们先搞两个链表去接受 headA和 headB
- 其次我们就要把我们的链表长度保持一致
- 首先计算出 headA 和 headB的长度
- 然后将长的那个链表移动到和短的链表保持一致的长度
- 最后去循环遍历判断两个链表是否有一致的值. 如果有则返回
注意:
第一次记录链表长度的循环结束之后要记得重新为链表赋值
比较的是指针是否相同, 最后一个循环比较的是 nodeA == nodeB. 而不是 nodeA.val == nodeB.val
四、代码展示
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 两个链表, 接受 headA和 headB ListNode nodeA = headA; ListNode nodeB = headB; // 记录两个链表的长度 Integer skipA = 0, skipB = 0; // 计算出两个链表的长度 while(nodeA != null){ skipA++; nodeA = nodeA.next; } while(nodeB != null){ skipB++; nodeB = nodeB.next; } // 循环结束之后要重新为两个链表赋值 nodeA = headA; nodeB = headB; // 两个链表长度差 Integer n = skipA - skipB; // 让链表A为最长链表, 方便我们后续移动链表操作 if (skipA < skipB){ // 交换链表节点 ListNode node = nodeA; nodeA = nodeB; nodeB = node; // 如果B链表长. 那么长度差是负值, 所以这里要重新进行计算 n = skipB - skipA; } // n是长度差, 缩短链表A至长度与B相等 while(n-- > 0 ){ nodeA = nodeA.next; } // 记录返回值 ListNode node = null; // 循环判断链表值是否相等 while(nodeA != null){ // 如果两个值相等, 则跳出循环 if (nodeA == nodeB){ return nodeA; } nodeA = nodeA.next; nodeB = nodeB.next; } return null; } 复制代码
五、提交代码
网络异常，图片无法展示
|
注: 刷 LeetCode感觉自己做对了, 但是测试是错的时候, 一定要看评论区, 肯定是有哪里自己没有考虑到
