【LeetCode链表#12】链表相交

链表相交

同：160.链表相交

力扣题目链接(opens new window)

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

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

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

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

示例 1：

示例 2：

示例 3：

思路

根据LeetCode题目下的隐藏提示4以及观察可知：

如果两个链表存在相交部分，那么自相交点之后的节点应该都是重合的(下面的图没体现出来)

由此，我们可以将待判断的两个链表的尾部对齐

将较长链表的当前指针指向与短链表的对齐

面试题02.07.链表相交_2

从此处同时向后遍历，直到找到相同的节点

思路大概是这样的，那么关键要解决两个问题：

1、如何找出较长的那个链表？

2、如何尾部对齐？

因为我们有两个链表，那么先直接定义两个指针curA和curB，并且，curA一定是指向较长的那个链表的指针。

实际上第一个问题用遍历解决就行了，但是在过程中，万一最开始定义的链表并不是最长的，应该如何处理？例如curA实际上比curB短，这时需要将两者调换

调换过程也比较简单粗暴，当记录长度的变量显示curA比curB短后，将curA和curB交换就行（同时还要将长度变量互换）

这个时候，求出两链表的长度差，将curA移动到curB所在的位置，就能将尾部对齐

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //初始化两链表的头节点，默认A为较长的那个
        ListNode curA = headA;
        ListNode curB = headB;

        //用于记录链表长度
        int lenA = 0;
        int lenB = 0;

        //分别遍历获取两链表长度
        while(curA != null){
            lenA++;
            curA = curA.next;
        }

        while(curB != null){
            lenB++;
            curB = curB.next;
        }

        //遍历结束重新将指针放回头节点
        curA = headA;
        curB = headB;


        //如果lenB大，就要交换一下
        if(lenB > lenA){
            //交换节点
            ListNode tempN;
            tempN = curA;
            curA = curB;
            curB = tempN;

            //交换长度信息
            int tempL = lenA;
            lenA = lenB;
            lenB = tempL;
        }

        //尾部对齐
        //先计算长度差值
        int subResult = lenA - lenB;
        //移动指针对齐短链表
        while(subResult-- > 0){
            curA = curA.next;
        }

        //两链表同时向后遍历，遇到相同值便返回
        while(curA != null){
            if(curA == curB){
                return curB;//A、B都行
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;   
    }
}