算法小知识------10.16-----相交链表
相交链表
该题出自力扣的160题相交链表(简单题),正巧对之前的数组链表等知识做一次巩固与练习
温故而知新
关于链表,简单的回顾一下。
链表,基于线性的数据结构,基本由下一节点与当前节点的值组成(如果为双向链表,则多出上一节点存储),更适用于写操作频繁的业务场景。
审题
简述题目:
给出两个链表,判断其是否有相交节点,有则输除,无则输出null。
思路:
题目需要求出的是两个链表的相交节点,从两个链表来说,可以采用双指针方法
由于两个链表长度不一定一致,所以双指针方式分别指向两个链表的头节点
由于两个链表同时移动指针,第一轮走完,就抹除了大小差
以大小为例:A=4,B=5; A≠B;A+B = B+A;
从第二轮开始,如果两个链表有相交则输出,没有就为null
代码实现
先对两个链表判空
再用两个变量指针指向两个链表
循环当两个链表不一致时
一个链表走完指向另一个链表的头结点
输出
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } **/ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //链表双指针:第一轮双指针同同时行走,抹掉距离差,第二轮相交则为有交集 if (headA == null || headB == null){ return null; } ListNode pA = headA; ListNode pB = headB; while(pA != pB){ pA = pA == null?headB:pA.next; pB = pB == null?headA:pB.next; } return pA.val; }复制代码
作者:Jayhaw_花
链接:https://juejin.cn/post/7019486871361159182