面试题 02.07. 链表相交
本文最后更新于633 天前,其中的信息可能已经过时,如有错误请发送邮件到tomding1065@gmail.com



题目链接/文章讲解:https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

1.这个题我在以前的练习中遇到过,我在刚看到这个题的第一个想法就是这个,就是个数学题,我想着这个题好像挺需要数学一点点计算的,然后要有点想象力,其实自己画个图也能解决呢。

2.这个题的难点在于我不知道怎么判断什么时候有环,就算有环我也不知道怎么确定这个环的入口,卡哥的视频真的对于这个题给了我很大的启发,让我知道这样的思路,也让我明白了,这个题的关键是,入口的节点不是值相等,而是指针相等,这个我还是理解了一会的,总之结果还是让我满意的,这个题对于现阶段的我的难度还是有的,我会在一段时间后复习一下这个题的,为此我特意准备一个题单,到时候复习的时候将我认为,值得多做几遍,或者是我认为有难度的题,放在一个分类里。

CPP

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        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;

        if(lenB>lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }

        int gap = (lenA -lenB);

        while(gap--){
            curA = curA->next;
        }
        while(curA != NULL){
            if(curA == curB){
               return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;

    }
};
文末附加内容
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
Cream_dpl