题解 | #两个链表的第一个公共结点#双指针相遇

解法1:双指针遍历

指针A先遍历链表1，结束了再遍历链表2

指针B先遍历链表2， 结束了再遍历链表1

相遇时：

1.如果有公共节点

假设链表1不在公共节点的部分长度为a1，在公共节点的长度为b，

链表2不在公共节点的部分长度为a2，在公共节点的长度为b

A和B走过了相同的节点数total，A在链表2上走过的节点数为x, B在链表2上走过的节点数为y,

total = a1 + b + x

total = a2 + b + y

很容易得出：x = a2, y = a1

也就是说，他们第二圈会走到第一个相同的节点相遇

2.如果没有相同的节点

那么它会走到链表末尾时等于null而相等

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        if (pHead1 == pHead2) {
            return pHead1;
        }
        ListNode pointer1 = pHead1;
        ListNode pointer2 = pHead2;
        while (pointer1 != pointer2) {
            pointer1 = (pointer1 == null) ? pHead2 : pointer1.next;
            pointer2 = (pointer2 == null) ? pHead1 : pointer2.next;
        }
        return pointer1;
    }
}

时间复杂度分析：O(M+N)

空间复杂度分析：O(1)

解法2:计算链表长度 + 双指针

分别计算链表长度，找出他们长度的差值k，长的链表先走k步，然后比较两个指针，相等的话就是第一次相遇

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        if (pHead1 == pHead2) {
            return pHead1;
        }
        int length1 = getLength(pHead1);
        int length2 = getLength(pHead2);

        int diff = 0;
        ListNode goFirst = null;
        ListNode goLater = null;
        if (length1 <= length2) {
            diff = length2 - length1;
            goFirst = pHead2;
            goLater = pHead1;
        } else {
            diff = length1 - length2;
            goFirst = pHead1;
            goLater = pHead2;
        }

        while (diff != 0) {
            goFirst = goFirst.next;
            diff--;
        }

        while (goFirst != goLater) {
            goFirst = goFirst.next;
            goLater = goLater.next;
        }
        return goFirst;

    }

    private int getLength(ListNode head) {
        ListNode pointer = head;
        int length = 0;
        while (pointer != null) {
            pointer = pointer.next;
            length++;
        }
        return length;
    }
}

复杂度分析

时间复杂度：计算链表长度需要O(m)/O(n), 在移动指针也是O(m)/O(n)，最后将两个时间复杂度相加

空间复杂度：O(1)

不考虑时间或者空间复杂度的话也可以考虑以下的解法：

解法3:比较两个链表的倒数第k个节点，从后往前找，直到找到最前的一个相同的节点

复杂度分析

时间复杂度：找倒数第k个节点需要O(n), 找k次倒数第k个节点需要k*O(n)次， 总共是O(n平方)

空间复杂度：O(1)

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        if (pHead1 == pHead2) {
            return pHead1;
        }
        // phead1 的倒数第k个节点和phead2的倒数第k个节点相同，但是倒数第k+1 个节点不同
        int indexFromEnd = 1;
        ListNode lastKOfPhead1 = findKthNodeFromEnd(pHead1, 1);
        ListNode lastKOfPhead2 = findKthNodeFromEnd(pHead2, 1);
        ListNode lastSameNodeFromEnd = null;
        while (lastKOfPhead1 == lastKOfPhead2) {
            lastSameNodeFromEnd = lastKOfPhead1;
            indexFromEnd++;
            lastKOfPhead1 = findKthNodeFromEnd(pHead1, indexFromEnd);
            lastKOfPhead2 = findKthNodeFromEnd(pHead2, indexFromEnd);
        }
        return lastSameNodeFromEnd;
    }

    public ListNode findKthNodeFromEnd(ListNode head, int k) {
        if (k == 0 || head == null) {
            return head;
        }
        if (head.next == null && k == 1) {
            return head;
        }

        if (head.next == null && k > 1) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        int count = 1;
        while (count < k && fast.next != null) {
            fast = fast.next;
            count++;
        }
        if (count < k) {
            return null;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

解法4:空间足够的话可以使用栈

所有的节点入栈，一个一个比较，直到找到不一样的节点为止

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        if (pHead1 == pHead2) {
            return pHead1;
        }
        Stack<ListNode> visited1 = new Stack<ListNode>();
        Stack<ListNode> visited2 = new Stack<ListNode>();
        ListNode pointer1 = pHead1;
        while (pointer1 != null) {
            visited1.push(pointer1);
            pointer1 = pointer1.next;
        }

        ListNode pointer2 = pHead2;
        while (pointer2 != null) {
            visited2.push(pointer2);
            pointer2 = pointer2.next;
        }
        ListNode theLastSameNodeFromEnd = null;
        pointer1 = visited1.pop();
        pointer2 = visited2.pop();
        while (pointer1 == pointer2) {
            theLastSameNodeFromEnd = pointer1;
            if(visited1.empty() || visited2.empty()){
                break;
            }
            pointer1 = visited1.pop();
            pointer2 = visited2.pop();
        }

        return theLastSameNodeFromEnd;
    }
}