您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

相交链表(图文)

第十三双眼睛2023-11-30【数据结构与算法】人已围观

简介相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路：最容易想到的，就是先遍历任意一个链表，把节点存入一个Map，然后开始遍历另一个链表，每遍历到一个节点，判断这个节点是否存在于Map中，如果存在，这个节点就是他们相交点，如果遍历完了，还是没有找到相交点，就是不存在。代码如下：

public static ListNode method1(ListNode headA, ListNode headB) {
   Map<ListNode, ListNode> map = new HashMap<>();
   ListNode current = headA;
   while (true) {
       if (current == null) {
           break;
       }
       if (!map.containsKey(current)) {
           map.put(current,current);
           current = current.next;
       }
   }
   current = headB;
   while (true) {
       if (current == null) {
           break;
       }
       if (map.containsKey(current)) {
           return current;
       }
       current = current.next;
   }
   return null;
}

思路二：
链表A加链表B的长度肯定是一定的，定义两个辅助节点，分别指向两个链表的头部，开始遍历，如果为空了，就换到另一个链表的头部，继续开始遍历，如果他们最后都为空，那么两个链表不相交，如果他们在某一个节点相等了，那么这就i是交点。代码如下：

public static ListNode method2(ListNode headA, ListNode headB) {
   if (headA == null || headB == null) {
       return null;
   }
   ListNode pa = headA;
   ListNode pb = headB;
   while (true) {
       if (pa == null && pb == null) {
           return null;
       }
       if (pa == pb) {
           return pa;
       }
       if (pa != null) {
           pa = pa.next;
       } else {
           pa = headB;
       }
       if (pb != null) {
           pb = pb.next;
       } else {
           pb = headA;
       }
   }
}

Tags：

很赞哦！ ()

上一篇：环形链表(图文)

下一篇：Excel表列名称(图文)