160. 相交链表

双重遍历

public class Solution {
  // 链表的节点完全相同应该就好理解了，并不是节点中的值相同。地址内存相同
  // 你不知道后面是否有跟前面一样的点
  // 双重遍历
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      while (headA != null) {
          ListNode temp = headB;
          while (temp != null) {
              if (headA == temp)
                  return headA;
              temp = temp.next;
          }
          headA = headA.next;
      }
      return null;
  }
}

哈希表

public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      HashSet<ListNode> hs = new HashSet<ListNode>();
      while(headA!=null) {
          hs.add(headA);
          headA = headA.next;
      }
      while(headB!=null) {
          if(hs.contains(headB))
              return headB;
          headB = headB.next;
      }

      return null;
  }
}

双指针

public class Solution {
  // 链表的节点完全相同应该就好理解了，并不是节点中的值相同。地址内存相同
  // 你不知道后面是否有跟前面一样的点
  // 双重遍历
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      int lenA = 0;
      int lenB = 0;
      ListNode tempA = headA;
      ListNode tempB = headB;
      while(tempA!=null) {
          lenA++;
          tempA = tempA.next;
      }
      while(tempB !=null) {
          lenB++;
          tempB = tempB.next;
      }
      if(lenA>lenB) {
          for(int i = 0 ; i < lenA-lenB ; i++) {
              headA = headA.next;
          }
      }
      else {
          for(int i = 0 ; i < lenB - lenA; i++) {
              headB = headB.next;
          }
      }
      while(headB!=null&&headA!=null) {
          if(headB == headA) {
              return headB;
          }
          else {
              headB = headB.next;
              headA = headA.next;
          }
      }
      return null;
  }
}