160.相交链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了160.相交链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2971字，纯文字阅读大概需要5分钟。

内容图文

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;
    }
}

内容总结

以上是互联网集市为您收集整理的160.相交链表全部内容，希望文章能够帮你解决160.相交链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---