Leetcode刷题日记11-27：剑指 Offer 52. 两个链表的第一个公共节点

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

如下面的两个链表**：**

示例

在节点 c1 开始相交。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ne8i8gnf-1637994719147)(F:MyPostGraduate柳骏杰刷题日记Leetcode刷题日记11-27：剑指 Offer 52. 两个链表的第一个公共节点160_statement.png)]
注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

这道题有两种思路

• 一种
  • 先计算两个链表各自的长度lengthA和lengthB
  • 利用长度，将两个链表放到同一遍历起跑点
  • 最后遍历就行

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //先确定长度,分别计算两个链表的长度。 2n
        int lengthA=0;
        int lengthB=0;
        ListNode nodeA=headA;
        ListNode nodeB=headB;
        while(nodeA !=null){
            lengthA++;
            nodeA=nodeA.next;
        }
        while(nodeB !=null){
            lengthB++;
            nodeB=nodeB.next;
        }
        //对齐两个链表的长度。
        nodeA=headA; //还原，指向头节点
        nodeB=headB;
        //A链表比较长，对齐B链表
        if(lengthA>lengthB){
            while(lengthA !=lengthB){
                nodeA=nodeA.next;
                lengthA--;
            }
        }
        //B链表比较长，对其A链表
        if(lengthB>lengthA){
            while(lengthA !=lengthB){
                nodeB=nodeB.next;
                lengthB--;
            }
        }
        //现在两个链表长度一致，可以遍历一次确定相交节点
        while(nodeA!=null){
            if(nodeA==nodeB){
                return nodeA;
            }
            nodeA=nodeA.next;
            nodeB=nodeB.next;          
        }
        //如果没找到,返回null
        return nodeA;

    }
}

• 第二种
  • 假设两个链表的长度分别为a和b，然后两个链表相交的链表长度为c
  • 所以如果两个链表有相交的地方则
    • $ a+(b-c)=b+(a-c)$
  • 否则 a + b = b = c a+b=b=c a+b=b=c

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode n1 = headA;
        ListNode n2 = headB;
        
        while(n1 != n2){
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n1;
    }
}