相交链表

相交链表(不存在环)

解法一(哈希表)

1. 第一步：创建哈希表，将第一个链表塞入哈希表
2. 第二步：将链表二塞进哈希表，如果链表二全部可以塞进去，说明不相交，繁殖链表相交

/**
 * 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) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode temp = headA;
        while (temp != null) {
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null){
            if (set.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

解法二(双指针)

1. 第一步：从头到尾遍历链表A和B获取链表长度

2. 第二步：将链表长度做差值n

3. 第三步：将较长的链表从头开始遍历，遍历n的长度

4. 第四步：两个链表同时遍历，比较两个链表的地址，若相同则说明找到了交点

/**
 * 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) {
      if(headA==null || headB==null){
        return null;
      }
      ListNode curr1 = headA;
      ListNode curr2 = headB;
      
      int n = 0;
      //遍历到链表节点最后一个位置，并没有遍历到空
      //重复使用n变量降低空间复杂度
      while(curr1.next != null){
        n++;
        curr1 = curr1.next;
      }
      while(curr2.next != null){
        n--;
        curr2 = curr2.next;
      }
      
      //让curr1指向长的链表
      curr1 = n>0 ? headA : headB;
      curr2 = curr1==headA? headB:headA;
      n = Math.abs(n);
      
      
        while(n!=0){
          n--;
          curr1 = curr1.next;
        }
        
        //最坏的情况，A和B没有交点，都遍历到空，退出循环
        while(curr1 != curr2){
          curr1 = curr1.next;
          curr2 = curr2.next;
        }
      	return curr1;
    }
}