lintcode 380. 两个链表的交叉

r囧r小猫 2023-07-04 03:26 6阅读 0赞

请写一个程序，找到两个单链表最开始的交叉节点。

样例
    样例 1：
    
    输入：
    	A:          a1 → a2
    	                   ↘
    	                     c1 → c2 → c3
    	                   ↗            
    	B:     b1 → b2 → b3
    输出：c1
    解释：在节点 c1 开始交叉。
    样例 2:
    
    输入:
    Intersected at 6
    1->2->3->4->5->6->7->8->9->10->11->12->13->null
    6->7->8->9->10->11->12->13->null
    输出: Intersected at 6
    解释：begin to intersect at node 6.
    挑战
    需满足 O(n) 时间复杂度，且仅用 O(1) 内存。
    
    注意事项
    如果两个链表没有交叉，返回null。
    在返回结果后，两个链表仍须保持原有的结构。
    可假定整个链表结构中没有循环。

/**
     * Definition of singly-linked-list:
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *        this->val = val;
     *        this->next = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param headA: the first list
         * @param headB: the second list
         * @return: a ListNode
         */
        ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
        
            // write your code here
            set<ListNode*> A;
            while(headA) 
            {
        
                A.insert(headA);
                headA=headA->next;
            }
            while(headB)
            {
        
                if(A.count(headB)) return headB;
                headB=headB->next;
            }
            return NULL;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode511. 交换链表当中两个节点

给你一个链表以及两个权值v1和v2，交换链表中权值为v1和v2的这两个节点。保证链表中节点权值各不相同，如果没有找到对应节点，那么什么也不用做。样例样例

你的名字/ 2023年07月06日 06:22/ 0 赞/ 22 阅读

相关 lintcode 380. 两个链表的交叉

请写一个程序，找到两个单链表最开始的交叉节点。样例样例 1：输入： A: a1 → a2

r囧r小猫/ 2023年07月04日 03:26/ 0 赞/ 7 阅读

相关两个链表生成相加链表

两个链表生成相加链表 1、参考资料 https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b

我就是我/ 2022年12月04日 01:21/ 0 赞/ 169 阅读

相关合并两个链表c++_21 合并两个有序链表

01 题目信息 > 题目地址: > > https://leetcode-cn.com/problems/merge-two-sorted-lists/

朴灿烈づ我的快乐病毒、/ 2022年10月25日 04:52/ 0 赞/ 258 阅读

相关【链表】合并两个排序的链表

First \------ 递归思路，需要重新创建一个链表，空间复杂度O(1) ListNode Merge(ListNode pHead1, ListNode p

绝地灬酷狼/ 2022年09月25日 11:28/ 0 赞/ 217 阅读

相关交叉链表

两个单向链表，找出它们的第一个公共结点。链表的结点定义为： struct ListNode \{ int m\_nKey; ListNo

曾经终败给现在/ 2022年08月02日 09:57/ 0 赞/ 209 阅读

相关链表插入排序 lintcode

链表插入排序难度系数容易通过率 31% [ 描述][Link 1] [ 笔记][Link 2] [ 数据][Link 3] [ 评测][

ゝ一纸荒年。/ 2022年07月16日 12:09/ 0 赞/ 245 阅读

相关【LintCode 简单】451. 两两交换链表中的节点

1.问题描述：给一个链表，两两交换其中的节点，然后返回交换后的链表。 2.样例：给出 `1->2->3->4`, 你应该返回的链表是 `2->1->4

水深无声/ 2022年06月01日 05:50/ 0 赞/ 136 阅读

相关【LintCode 简单】165. 合并两个排序链表

1.问题描述：将两个排序链表合并为一个新的排序链表。 2.样例: 给出 `1->3->8->11->15->null`，`2->null`，返回 `1->2->

小灰灰/ 2022年06月01日 04:08/ 0 赞/ 191 阅读

相关 5，两个不交叉的有序链表的合并

思路：比较大小，控制指针指向，如果一个链表已经结束，则把剩下的链表加上去即可。注意：要判断输入时候正确。两个链表是否为空链表等特殊情况。

系统管理员/ 2022年05月26日 07:58/ 0 赞/ 131 阅读