链表相交问题

问题1

求链表是否有环

原理

• 可以使用快慢指针，如果快指针可以追上慢指针就说明有环

代码

public class Solution {
    public boolean hasCycle(ListNode head) {
       if(head==null){
           return false;
       }
       ListNode fast = head;
       ListNode slow = head;

       while(fast!=null&&fast.next!=null){
           fast = fast.next.next;
           slow = slow.next;
           if(slow==fast){
               return true;
           }
       }
       return false;
    }
}

注意事项

暂无

问题2

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

原理

• 判断链表是否有环可以使用快慢指针
• 如果判断了有环，如何找环的入口呢呢？这个其实是个数学问题，环的入口位置就在：head和slow同时开始，再次相遇的位置就是入口位置。

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
      if(head==null||head.next==null){
          return null;
      }
      ListNode fast = head;
      ListNode slow = head;
      while(fast!=null&&fast.next!=null){
          slow = slow.next;
          fast = fast.next.next;
          if(slow==fast){
              break;
          }
      }
      ListNode newHead = head;
      while(newHead!=null&&slow!=null){
         if(slow==newHead){
              break;
          }
          newHead = newHead.next;
          slow = slow.next;
         
      }
      return slow;
    }
}

注意事项

• 两次是否相等的判断是需要注意的，第一次是先移动后判断，第二次是先判断后移动。

问题3

找到两个单链表相交的起始节点，如果不相交返回为空。

原理

• 朋友们，请一定要珍惜身边的那个 ta 啊！你们之所以相遇，正是因为你走了 ta 走过的路，而 ta 也刚好走了你走过的路。这是何等的缘分！
  而当你们携手继续走下去时，你会慢慢变成 ta 的样子，ta 也会慢慢变成你的样子。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if(headA==null||headB==null){
           return null;
       }
       ListNode pa = headA;
       ListNode pb = headB;

       while(pa!=pb){
           pa = pa==null?headB:pa.next;
           pb = pb==null?headA:pb.next;
       }
       return pa;
    }
}

注意事项

• 当pa==null的时候重新从headB开始，反之pb==null的时候重新从headA开始