[剑指offer][Java]两个链表的第一个公共节点

题目

输入两个链表，找出它们的第一个公共结点。

程序核心思想

首先判断这个两个链表有没有环。https://www.jianshu.com/p/2d229077ce10

• 如果这个两个链表都没有环，则 无环结构.png
  

  如何找到公共节点呢？可以先求出两个链表的长度差，让长的链表先走长度差步，然后两个链表一起走，直到有相同的节点则返回，否则如果一个链表走到null了，则返回null。

• 如果这个两个链表都有环，就有三种结构： 有环结构.png
  

  先比较两个链表的环的入口节点是否相同，如果相同则是第二种结构，那么可以用无环的做法来做。
  如果环的节点不同，则是第三或第四种情况，可以标记一个链表的入环节点，然后遍历，如果在环上出现跟第二个链表的入环节点相同的节点，则是第三种情况，返回任意一个入环节点即可，否则是第一种情况，返回null。

• 如果这两个链表一个有环一个没有环，则它们没有公共节点。

Tips

注意链表为空的情况，要返回null，否则会出现空指针异常。

代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode loop1 = getLoop(pHead1);
        ListNode loop2 = getLoop(pHead2);
        
        if(loop1 == null && loop2 == null){
            return noLoop(pHead1, pHead2);
        }
        if(loop1 != null && loop2 != null){
            return bothLoop(pHead1, pHead2, loop1, loop2);
        }
        return null;
    }
    
    public ListNode getLoop(ListNode head){
        if(head == null)    return null;
        ListNode slow = head;
        ListNode fast = head;
        if(slow.next != null){
            slow = slow.next;
        }else{
            return null;
        }
        if(slow.next != null){
            fast = slow.next;
        }else{
            return null;
        }
        
        while(fast.next != null && fast.next.next != null){
            if(fast != slow){
                fast = fast.next.next;
                slow = slow.next;
            }else{
                fast = head;
                while(true){
                    if(fast == slow){
                        return fast;
                    }else{
                        fast = fast.next;
                        slow = slow.next;
                    }
                }
            }
        }
        return null;
    }
    
    public int getLen(ListNode head){
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        return len;
    }
    
    public int getLen(ListNode head, ListNode end){
        int len = 0;
        while(head != end){
            len++;
            head = head.next;
        }
        return len + 1;
    }
    
    public ListNode noLoop(ListNode headA, ListNode headB){
        int len1 = getLen(headA);
        int len2 = getLen(headB);
        return NoLoop(headA, headB, len1, len2);
    }
    
    public ListNode NoLoop(ListNode headA, ListNode headB, int len1, int len2){
        if(len1 > len2){
            for(int i = 0; i < len1 - len2; i++){
                headA = headA.next;
            }
        }else{
            for(int i = 0; i < len2 - len1; i++){
                headB = headB.next;
            }
        }
        while(headA != null){
                if(headA != headB){
                    headA = headA.next;
                    headB = headB.next;
                }else{
                    return headA;
                }
        }
        return null;
    }
    
    public ListNode bothLoop(ListNode headA, ListNode headB, ListNode loop1, ListNode loop2){
        int len1 = getLen(headA, loop1);
        int len2 = getLen(headB, loop2);
        if(loop1 == loop2){
            return NoLoop(headA, headB, len1, len2);
        }else{
            ListNode temp = loop1.next;
            while(temp != loop1){
                if(temp == loop2){
                    return len1 > len2 ? loop2 : loop1;
                }else{
                    temp = temp.next;
                }
            }
            return null;
        }
    }
}