力扣每日一题 160. 相交链表

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null

题目数据 保证 整个链式结构中不存在环。

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

今天出了个简单题,总算可以喘口气,做了这么些题,链表题相对来说比较直观简单,一般双指针可以解决。

这个题是判断两个链表是否存在交点。直观方式是遍历第一个链表,将链表节点存入hashset,然后遍历第二个链表,碰到的第一个存在于hashset中的节点,则为交点,时间复杂度为O(n),需要点额外空间来存储链表一的节点。

还有一种方式,同时遍历两个链表,链表一的指针遍历完,则开始遍历链表二,链表二的指针遍历完,则开始遍历链表一,如果两指针相等,则退出循环。

这种方式基于:两个指针遍历的长度肯定是相等的(A+B=B+A),两指针相等的情况下,要么是找到了交点,要么两指针都为null,这两种情况都可以返回。

 1  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 2         if (headA == null || headB == null) {
 3             return null;
 4         }
 5         ListNode pA = headA, pB = headB;
 6         while (pA != pB) {
 7             pA = pA == null ? headB : pA.next;
 8             pB = pB == null ? headA : pB.next;
 9         }
10         return pA;
11     }

 

上一篇:CF990G GCD Counting(树上莫比乌斯反演,分层图,并查集)


下一篇:Leetcode 160.相交链表