相交链表
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=study-plan-v2&envId=top-100-liked
我的解答：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> set = new HashSet<>(); ListNode cur = headA; while(cur!=null){ set.add(cur); cur = cur.next; } cur = headB; while(cur!=null){ if(set.contains(cur)){ return cur; } cur = cur.next; } return null; }分析：代码的时间复杂度为O(m+n)，空间复杂度为O(m)，m为链表A的长度。自己未能想出时间复杂度为O(m+n)且空间复杂度为O(1)的解法。采用哈希集合解题，先将链表A的所有节点存入set集合中，然后遍历链表B判断每个节点是否已经存在于集合中，若存在，则此节点为相交的起始节点。
看了官方题解后的解答：
//方法一：哈希集合（解题思路与我的解答一致） //时间复杂度：O(m+n) //空间复杂度：O(m)，m为链表A的长度 //方法二：双指针 //时间复杂度：O(m+n) //空间复杂度：O(1) //只看思路编写的代码： public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA, pB = headB; while(pA!=null && pB!=null){ if(pA==pB){ return pA; } pA = pA.next; pB = pB.next; } if(pA!=null){ pB = headA; while(pA!=null){ pA = pA.next; pB = pB.next; } pA = headB; } else if(pB!=null){ pA = headB; while(pB!=null){ pA = pA.next; pB = pB.next; } pB = headA; } while(pA!=null && pB!=null){ if(pA==pB){ return pA; } pA = pA.next; pB = pB.next; } return null; } //看了思路和代码后编写的代码： public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA, pB = headB; while(pA!=pB){ pA = pA==null ? headB : pA.next; pB = pB==null ? headA : pB.next; } return pA; }分析：
方法二的解题思路：起始两个指针分别指向两个链表的头节点，然后同时向后移动，若两个链表的长度相等，那么两个指针会同时指向相交节点或null；若两个链表长度不相等，假设此时指向较短链表的指针为pA，指向较长链表的指针为pB，那么当pA移动到null时，pB剩余的步数就是两个链表的长度之差，这时我们将pA指向较长链表的头节点，然后继续同时移动两个指针，当pB指向null时，pA指针恰好走过了较长链表多出的那部分，此时我们让pB指向较短链表的头节点，再让pA和pB同时移动，移动到相同节点或null时返回其中一个指针就是答案。
总结
- 本题可采用双指针解法来降低空间复杂度，双指针解法的关键在于当两个链表长度不相等时，如何同步两个指针的移动，关键思路就是让两个指针同时移动，当其中一个指针指向null时，另一个指针剩余的步数就是两个链表的长度之差，根据这点就可以轻松地实现两个两个指针的同步。
