阅读 75

算法小知识------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;
    }复制代码

1634351833(1).jpg


作者:Jayhaw_花
链接:https://juejin.cn/post/7019486871361159182


文章分类
后端
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐