大家好本频道是逻辑自洽的今天给大家讲解leeeCode160题——相交链表。今后还会持续更新计算机相关知识趣闻以及一些算法题。FOLLOW关注我逻辑自洽题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。举个直观例子链表A1 → 2 → 3 → 4 → 5链表B6 → 7 → 3 → 4 → 5这两个链表在节点3的位置相交最终要返回节点3如果两个链表完全独立没有公共节点就返回null。解法1哈希表/哈希集合中等效率思路易懂利用集合的去重性遍历两条链表将每个节点都存入集合中。遍历的同时判断集合里是否已经有相同的节点。/** * 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) { HashSetListNode set new HashSet(); ListNode l headA; while(l!null){ set.add(l); ll.next; } lheadB; while(l!null){ if(set.contains(l)){ return l; } ll.next; } return null; } }时间复杂度O(mn)只需要两次单独遍历空间复杂度O(m)需要额外存储一个链表的所有节点占用内存。解法2双指针法最优解O(1)空间让指针A从A链表开始指针B从B链表开始当任意一个指针指向链表末尾时就让它继续从另一条链表的头部开始遍历。如果有交点那么它们一定会相遇。通俗比喻两个人走路路程相等就会相遇想象有两个人分别从链表A和链表B的头节点出发速度一样一直往前走指针pA走链表A走到末尾后转头走链表B指针pB走链表B走到末尾后转头走链表A因为两人走的总路程完全一样如果链表相交一定会在相交节点相遇如果不相交两人会同时走到null。核心逻辑推导假设链表A长度a c链表B长度b cc是相交部分的长度a、b是各自独有的长度。pA总路程a c bpB总路程b c a两者路程相等所以一定会同时到达相交节点完美避开长度差的问题/** * 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) { //双指针 ListNode LAheadA; ListNode LBheadB; while(true){ if(LALB){ //当双方指向同一地址时循环结束。当不存在交点时都为null循环结束 break; } LA(LAnull)?headB:LA.next; //如果LA走到A链表末尾就会自动走到B链表的头节点 LB(LBnull)?headA:LB.next; } return LA; //返回LALB都行 } }我走过你走过的路你也走过我走过的路若有缘我们都会在交点相逢。若无缘在热寂宿命的宇宙我们也终会相遇于时间终点。