思路及解答HashSet包含法

第⼀种做法直接依赖于 HashSet 遍历第⼀个链表的时候将所有的节点添加到 hashset 中遍历第⼆个链表的时候直接判断是否包含即可属于空间换时间的做法。javapublic ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 null || pHead2 null) return null; // 使用HashSet存储第一个链表的所有节点 HashSetListNode visited new HashSet(); // 遍历第一个链表将所有节点加入集合 ListNode current pHead1; while (current ! null) { visited.add(current); current current.next; } // 遍历第二个链表检查节点是否在集合中 current pHead2; while (current ! null) { if (visited.contains(current)) { return current; // 找到第一个公共节点 } current current.next; } return null; // 没有公共节点 }​时间复杂度​O(mn)需要遍历两个链表各一次​空间复杂度​O(min(m,n))存储较短链表的节点双栈法利用栈的后进先出特性从链表尾部开始比较找到最后一个相同的节点。公共节点之后的节点都是相同的所以从后往前比较最后一个相同的节点就是第一个公共节点javaimport java.util.Stack; public class Solution { /** * 使用双栈查找两个链表的第一个公共节点 * 思路将两个链表分别压入栈中然后同时出栈比较 * 时间复杂度O(mn)空间复杂度O(mn) */ public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 null || pHead2 null) return null; StackListNode stack1 new Stack(); StackListNode stack2 new Stack(); // 将两个链表的所有节点分别压入栈中 ListNode current pHead1; while (current ! null) { stack1.push(current); current current.next; } current pHead2; while (current ! null) { stack2.push(current); current current.next; } ListNode commonNode null; // 同时从两个栈弹出节点进行比较 while (!stack1.isEmpty() !stack2.isEmpty()) { ListNode node1 stack1.pop(); ListNode node2 stack2.pop(); if (node1 node2) { commonNode node1; // 记录公共节点 } else { break; // 遇到不同节点停止比较 } } return commonNode; } }时间复杂度​O(mn)需要遍历两个链表各两次压栈和出栈​空间复杂度​O(mn)需要两个栈存储所有节点长度差法推荐可以将两个链表想象为两段路程公共节点是终点。让长的链表先走多出的距离然后同时前进就能同时到达公共节点譬如现在有⼀个链表 1-2-3-6-7 另外⼀个链表 4-5-6-7 明显可以看出第⼀个公共节点是6 。最直接的⽅法每⼀个链表都遍历⼀次计算链表中的个数⽐如 1-2-3-6-7 个数为5 4-5-6-7 个数为4两者相差1设为k个。我们可以使⽤两个指针分别指向链表的头部。然后让第⼀个链表的指针先⾛ k1 步。这样就相当于指针后⾯的两个链表等⻓了。就可以开始⽐较如果不相等则两个指针都往后移动即可知道节点为null。java/* public class ListNode { int val; ListNode next null; ListNode(int val) { this.val val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { // 只要有⼀个为空就不存在共同节点 if (pHead1 null || pHead2 null) { return null; } // 计算链表1中的节点个数 int numOfListNode1 0; ListNode head1 pHead1; while (head1 ! null) { numOfListNode1; head1 head1.next; } // 计算链表2中节点个数 int numOfListNode2 0; ListNode head2 pHead2; while (head2 ! null) { numOfListNode2; head2 head2.next; } // ⽐较两个链表的⻓度 int step numOfListNode1 - numOfListNode2; if (step 0) { // 链表1更⻓链表1移动 while (step ! 0) { pHead1 pHead1.next; step--; } } else { // 链表2更⻓链表2移动 while (step ! 0) { pHead2 pHead2.next; step; } } // 循环遍历后⾯的节点相等则返回 while (pHead1 ! null pHead2 ! null) { if (pHead1 pHead2) { return pHead1; } else { pHead1 pHead1.next; pHead2 pHead2.next; } } return null; } }时间复杂度​O(mn)需要遍历链表三次两次计算长度一次查找​空间复杂度​O(1)只使用常数级别额外空间但是上⾯的做法如果公共节点在最后⼀个假设⼀个链表⻓度为 n ⼀个为 m 那么计算个数就要全部遍历需要 nm 。两个链表都移动到最后⼀个节点的时候才相等也是 nm 也就是 O(2*(nm)) 。双指针遍历法最优有没有更加好⽤的做法呢肯定有我们来看两个链表分别是如果我在第⼀个链表后⾯拼接上第⼆个链表第⼆个链表后⾯拼接上第⼀个链表就会变成下⾯的样⼦发现了⼀个规律也就是拼接之后的链表是等⻓度的第⼀个和第⼆个链表都从第⼀个开始⽐较只要相等就说明是第⼀个公共节点。也就是上⾯被圈起来的 6 节点。原理如下设链表1独有部分长度为a链表2独有部分长度为b公共部分长度为c指针p1路径a c b指针p2路径b c a两个指针路径长度相同会在公共节点相遇特殊情况处理​​当两个链表没有公共节点时两个指针会同时变为null退出循环javapublic class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { // 只要有⼀个为空就不存在共同节点 if (pHead1 null || pHead2 null) { return null; } ListNode head1 pHead1; ListNode head2 pHead2; while (head1 !head2) { // 如果下⼀个节点为空则切换到另⼀个链表的头节点否则下⼀个节点 head1 (head1 null) ? pHead2 : head1.next; head2 (head2 null) ? pHead1 : head2.next; } return head1; } }时间复杂度​O(mn)每个指针遍历两个链表各一次