160.相交链表---链表(Java）

2024-04-22 02:48

文章标签 java 链表相交 160

本文主要是介绍160.相交链表---链表(Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
请添加图片描述
题目数据保证整个链式结构中不存在环。

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

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。
请添加图片描述

规律：
1.如果链表A和链表B不相交，则它们最后都会走到空的位置。
2.当指针 pointA 遍历到链表 A 的尾节点时，此时指针 pointA 走了 a 个节点，将指针 pointA 指向链表 B 的头部，继续向后遍历，直至走到 c1，此时指针 pointA 总共走了 a + ( b - c ) 步。
当指针 pointB 遍历到链表 B 的尾节点时，此时指针 pointB 走了 b 个节点，将指针 pointB 指向链表 A 的头部，继续向后遍历，直至走到 c1，此时指针 pointB 总共走了 b + ( a - c ) 步。
根据数学知识，a + ( b - c ) = b + ( a - c ) ，如果 c > 0，表明两链表有公共尾部， c1 存在，两两链表同时到达 c1；如果 c = 0，表明两链表没有公共尾部，指针 pointA 和 pointB 都指向 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) {if(headA == null || headB == null) return null;//边界条件，如果链表A和链表B的头节点都是空的就直接返回空了ListNode pointA = headA;//指针pointA指向头节点AListNode pointB = headB;//指针pointB指向头节点Bwhile(pointA !=  pointB){//链表A和链表B不相交，继续执行while循环if(pointA == null){//如果遍历到链表A的结尾pointA = headB;//把指针指向链表B继续遍历，直到链表A和链表B相交}else{pointA = pointA.next;//如果没有遍历到链表A的结尾，继续遍历}if(pointB == null){//如果遍历到链表B的结尾pointB = headA;//把指针指向链表A继续遍历，直到链表A和链表B相交}else{pointB = pointB.next;//如果没有遍历到链表B的结尾，继续遍历} }return pointA;//最后链表A和链表B相交，返回哪一个都行,headA 和 headB 不相交，那么 pointA 和 pointB 均为 null，也返回任意一个均可}
}