Leet160. 相交链表

1、问题2、解答3、代码解答package com.leetcode.hot100.linkedlist.Solution160; import java.util.HashSet; import java.util.Set; /** * 哈希集合的解决方案 * 时间复杂度O(mn)其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。 * 空间复杂度O(m)其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。 */ public class Solution160_1 { // 定义链表节点类 static class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } /** * 查找两个链表的相交节点哈希集合法 * param headA 链表A头节点 * param headB 链表B头节点 * return 相交节点无相交则返回null */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode visited new HashSet(); ListNode temp headA; // 遍历链表A将所有节点存入哈希集 while (temp ! null) { visited.add(temp); temp temp.next; } // 遍历链表B检查节点是否在哈希集中 temp headB; while (temp ! null) { if (visited.contains(temp)) { return temp; } temp temp.next; } // 无相交节点 return null; } /** * 测试方法 * 构建示例中的相交链表结构并验证结果 */ public static void main(String[] args) { Solution160_1 solution new Solution160_1(); // 1. 构建相交部分的节点 ListNode c1 new ListNode(5); ListNode c2 new ListNode(6); ListNode c3 new ListNode(7); c1.next c2; c2.next c3; // 2. 构建链表A: a1 - a2 - c1 - c2 - c3 ListNode a1 new ListNode(1); ListNode a2 new ListNode(2); a1.next a2; a2.next c1; // 3. 构建链表B: b1 - b2 - b3 - c1 - c2 - c3 ListNode b1 new ListNode(3); ListNode b2 new ListNode(4); ListNode b3 new ListNode(8); b1.next b2; b2.next b3; b3.next c1; // 4. 查找相交节点并输出结果 ListNode intersectionNode solution.getIntersectionNode(a1, b1); if (intersectionNode ! null) { System.out.println(相交节点的值为 intersectionNode.val); } else { System.out.println(两个链表没有相交节点); } // 测试无相交的情况 ListNode headC new ListNode(9); headC.next new ListNode(10); ListNode headD new ListNode(11); headD.next new ListNode(12); ListNode noIntersection solution.getIntersectionNode(headC, headD); if (noIntersection null) { System.out.println(测试无相交情况结果正确无相交节点); } } }package com.leetcode.hot100.linkedlist.Solution160; import java.util.concurrent.locks.ReentrantLock; /** * 双指针 * 时间复杂度O(mn)其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表每个指针遍历两个链表各一次。 * 空间复杂度O(1)。 */ public class Solution160_2 { // 定义单链表节点类 static class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } /** * 双指针法查找相交节点 * param headA 链表A头节点 * param headB 链表B头节点 * return 相交节点无相交则返回null */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) { return null; } ListNode pA headA, pB headB; // 当两个指针未相遇时循环 while (pA ! pB) { // pA走到末尾则跳转到headB否则走下一个节点 pA (pA null) ? headB : pA.next; // pB走到末尾则跳转到headA否则走下一个节点 pB (pB null) ? headA : pB.next; } // 相遇时pA/pB要么是相交节点要么是null无相交 return pA; } /** * 测试方法构建相交/不相交链表并验证结果 */ public static void main(String[] args) { Solution160_2 solution new Solution160_2(); // 测试1构建相交链表 // 相交部分c1(5) - c2(6) - c3(7) ListNode c1 new ListNode(5); ListNode c2 new ListNode(6); ListNode c3 new ListNode(7); c1.next c2; c2.next c3; // 链表Aa1(1) - a2(2) - c1 ListNode a1 new ListNode(1); ListNode a2 new ListNode(2); a1.next a2; a2.next c1; // 链表Bb1(3) - b2(4) - b3(8) - c1 ListNode b1 new ListNode(3); ListNode b2 new ListNode(4); ListNode b3 new ListNode(8); b1.next b2; b2.next b3; b3.next c1; ListNode intersection solution.getIntersectionNode(a1, b1); if (intersection ! null) { System.out.println(相交节点值 intersection.val); // 输出5 } else { System.out.println(无相交节点); } // 测试2构建不相交链表 ListNode headC new ListNode(9); headC.next new ListNode(10); ListNode headD new ListNode(11); headD.next new ListNode(12); ListNode noIntersection solution.getIntersectionNode(headC, headD); if (noIntersection null) { System.out.println(测试不相交结果正确无相交节点); } } }