02.07 链表相交

1、题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

2、初步作答

2.1 思路

• 题目已经给出不存在环，所以不需要考虑环的问题
• 链表相交，那么在相交之后的链表部分完全相同，那么我们可以采用类似快慢指针的方法去处理

2.2 做法

• 判断链表是否为空，如果存在空链表，则不可能存在相交节点，直接返回null
• 遍历链表，得到两条链表长度
• 移动长度较长的链表，使得两链表剩下部分链表长度一致
• 同时移动链表，直到两链表指针指到相同节点，返回节点

2.3 代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //用来保存头结点
    ListNode listNodeA = new ListNode(0);
    ListNode listNodeB = new ListNode(0);
    listNodeA.next = headA;
    listNodeB.next = headB;

    //记录A,B两个链表的长度
    int lengthA = 0;
    int lengthB = 0;
    while(headA.next != null){
        lengthA++;
        headA = headA.next;
    }
    while(headB.next != null){
        lengthB++;
        headB = headB.next;
    }

    //计算链表之差
    int num = (lengthB>=lengthA)?lengthB - lengthA:lengthA-lengthB;

    //使得链表处于同一起跑线
    headA = listNodeA.next;
    headB = listNodeB.next;
    if(lengthA >= lengthB){
        while(num > 0){
            headA = headA.next;
            num--;
        }
    }else{
        while(num > 0){
            headB = headB.next;
            num--;
        }
    }

    //寻找A,B两链表的交点
    while(headA != headB){
        headA = headA.next;
        headB = headB.next;
        //排除链表交点是空节点的可能
        if(headA == null || headB == null){
            System.out.println("null");
            return null;
        }
        num++;//用以记录链表移动的长度
    }

    //输出链表相交节点前分别有几个节点
    if(headA!=null){
        if(lengthA>=lengthB){
            System.out.println(Math.abs(lengthA-lengthB)+num);
            System.out.println(num);
        }else{
            System.out.println(num);
            System.out.println(Math.abs(lengthA-lengthB)+num);
        }
    }
    //返回相交节点
    return headA;
}

2.4 思考

• 如果链表有环的话，就不能采用这种方法。
  • 因为链表有环所以我们可以通过快慢指针得到入环的节点
  • 遍历到入环节点，得到两个链表的长度之后再使用上述部分算法

3、其余解法

• 来自力扣作者：jyd

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

• 来自K神的代码，算法思路一致，但是实现方法我简直看不下去我的代码，推荐看一下K神的代码解析

• 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/solution/mian-shi-ti-0207-lian-biao-xiang-jiao-sh-b8hn/