160.相交链表

解题思路

package leadcode;

import leadcode.lib.ListNode;

/**
 * @author : icehill
 * @description : 相交链表
 * 编写一个程序，找到两个单链表相交的起始节点。
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
 * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 * 注意：
 * <p>
 * 如果两个链表没有交点，返回 null.
 * 在返回结果后，两个链表仍须保持原有的结构。
 * 可假定整个链表结构中没有循环。
 * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 解题思路：
 * 正常做法就是遍历链表A，存到哈希表中，然后再遍历链表B，判断B是是否有节点在哈希表中，
 * 时间复杂度：O(n) 空间复杂度：O(n)
 * 空间复杂度超过题目要求O(1)
 * <p>
 * 最佳解法：双指针
 * 分析：如果链表相交，则两个链表相交节点开始到最后一个节点肯定都相同，设公共链表为k，k肯定小于等于min(lengthA,lengthB)
 * 链表长度分别我lengthA，lengthB，两个链表的长度差|lengthA-lengthB|，所以，相交点肯定不在max(lengthA,lengthB)的第|lengthA-lengthB|
 * 个节点，那么，只要长的链表先走|lengthA-lengthB|步，则以后每步只需要判断指针A、B，即可知道从什么时候开始相交，这样就能求出相交点了
 * 官方解法：
 * 也是双指针，只不过更巧妙，也更好理解，省去了我们上面的分析过程
 * 设置链表分别由各自独立的链表+公共链表组成，listA+listC、listB+listC
 * 分别拼接上listB跟listA，则两个链表长度相同，步数一样，遍历一遍，必定到相交节点
 * (其实跟我想的解决方法一样，就是把长度不同的链表变为相同，只不过我用减法，它用加法)
 * @date : 2021-04-17
 */
public class Solution160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lengthA = 1;
        int lengthB = 1;
        ListNode tailA = headA;
        ListNode tailB = headB;
        //计算两个链表的长度，以及尾结点
        while (tailA.next != null) {
            tailA = tailA.next;
            lengthA++;
        }
        while (tailB.next != null) {
            tailB = tailB.next;
            lengthB++;
        }
        //尾结点不一样，则两个链表并不相交，返回null
        if (tailA != tailB) {
            return null;
        }
        ListNode tempHeadA = headA;
        ListNode tempHeadB = headB;
        if (lengthA > lengthB) {
            int length = lengthA - lengthB;
            while (length > 0) {
                tempHeadA = tempHeadA.next;
                length--;
            }
        } else if (lengthA < lengthB) {
            int length = lengthB - lengthA;
            while (length > 0) {
                tempHeadB = tempHeadB.next;
                length--;
            }
        }
        while (tempHeadA != tempHeadB) {
            tempHeadA = tempHeadA.next;
            tempHeadB = tempHeadB.next;
        }
        return tempHeadA;
    }

    /**
     * 官方解法
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNodeTwo(ListNode headA, ListNode headB) {
        // 特判
        if (headA == null || headB == null) {
            return null;
        }

        ListNode head1 = headA;
        ListNode head2 = headB;

        while (head1 != head2) {
            if (head1 != null) {
                head1 = head1.next;
            } else {
                head1 = headB;
            }

            if (head2 != null) {
                head2 = head2.next;
            } else {
                head2 = headA;
            }
        }
        return head1;
    }
}