相交链表
数据结构与算法链表

注意:


如果两个链表没有交点,返回 null.

在返回结果后,两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。【此处由于存在时间和空间复杂度的限制,所以无法利用之前如通过HashSet 进行环形列表判断的方法,不满足空间复杂度,那么暴力遍历法也是不满足条件的


来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists


简单理解下题目,其实可以比喻成 路程A,运动员A及路程B,运动员B,运动员A和B的跑步速度是一致的,那么在总路程相同的情况下,运动员A和运动员B在同一时间起跑,那么肯定是能够同时到达终点的。


路程引申到这里可以理解为链表长度,那么如何保证路程距离相同呢?那就是遍历到链表尾结点的话就将指针指向另一个链表的头即可。


public class GetInsertSectionNode {

    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getInsertionNode(ListNode headA, ListNode headB) {
        if( headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

代码示例

暂无评论