Intersection of Two Linked Lists

• Easy
• key: list, cycle, Algs
• 类似: find cycle

Write a program to find the node at which the intersection of two singly linked lists begins.

• 要求:
  • 如果2个list没有merge, 那么返回null
  • 不能修改list
  • O(N) 时间和O(1)空间

idea 1

• 既然是找intersection, 就想到了cycle. 既然是cycle, 但是题目没有cycle, 那么就构造cycle. 所以我把listA首尾连接. 然后看listB有没有cycle, 如果有, 就找cycle的entrance. 这样我可以使用九章的hasCycle和entranceCycle, 这2个已知的算法.
• 代码如下:

public ListNode getIntersectionNodeJiuChap(ListNode headA, ListNode headB) {
    if (headA == null || headB == null)  return null;
    ListNode tmp = headA;
    while (headA.next != null) {  // 链接listA的首尾做成cycle.
      headA = headA.next;
    }
    headA.next = tmp;

    ListNode slow = headB;       // 使用九章找cycle的方法.
    ListNode fast = headB.next;
    while (slow != fast) {
      if (fast == null || fast.next == null) {  // 这里是判断是否有fast.next.next. 所以判断这2个. 记住这种判断的原因和写法
        return null;
      }
      fast = fast.next.next;
      slow = slow.next;
    }

    slow = headB;
    while (slow != fast.next) {  // 我一开始不记得算法了, 然后画了个草图发现是这样. 九章课上说了记住算法, 不用知道原理.
      slow = slow.next;
      fast = fast.next;
    }
    return slow;
  }

• 问题来了: 题目要求是不修改list的结构.
• 所以我改了一下, 改了headA之后, 最后再恢复. 果然就过了.

idea 2: 答案的做法.

• 不知道怎么想出来的
• 代码如下:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null)  return null;
    ListNode node1 = headA;
    ListNode node2 = headB;
    while (node1 != node2) {
      node1 = node1.next;
      node2 = node2.next;
      if (node1 == node2)  return node1;
      if (node1 == null)  node1 = headB;
      if (node2 == null)  node2 = headA;
    }
    return node1;
  }