代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 ,19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交 ,142.环形链表II

简介: 代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 ,19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交 ,142.环形链表II

写在前面,bad day。

一定要坚持住,真的要坚持住,养成习惯就好了。

今天很乱,也被各种事情搞得心烦。庆幸的是我今天没赖床,所有的题目都刷过了一遍,本来今天打算复盘一下昨天以前的题的。10点后就被迫去做一些无法推掉的社交,无法继续专心学习,节假日比工作还忙。我的作息是晚上10点睡4点起,因为下班后没精力学习算法。只好在上班之前把重要的事情先做完。

24. 两两交换链表中的节点

讲解链接

https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

自我思考

1 把不用交换的链表临时存储起来

2 把要交换的两个值的位置交换

3 再把断开的链表链接起来

4 当前节点移动到要交换的第一个节点之前

学习后的见解

同上

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* Dummy_head = new ListNode();
        Dummy_head->next = head;
        ListNode* curr = Dummy_head;
        while(curr->next!=nullptr && curr->next->next!=nullptr){
            ListNode* tmp_1 = curr->next;//准备交换的相邻两个节点的第一个位置
            ListNode* tmp_2 = curr->next->next->next; //把不动的节点先存储起来,用于与交换后的链表链接起来。
            curr->next = curr->next->next; //第一步,把相邻节点的第二个节点移动到前面,
            curr->next->next = tmp_1; // 第二步,把相邻节点的第一个移动至后面
            curr->next->next->next = tmp_2 ; // 移动完成后需要把后面的节点连接起来
            curr = curr->next->next; //移动到下一组相连节点前的节点,为移动他们做准备
        }
        return Dummy_head->next;
    }
};

总结

同样还是采用了虚拟头结点的方法,这样可以省去很多事。

19.删除链表的倒数第N个节点

讲解链接

https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

自我思考

暴力解解出来的

1 遍历节点,得到节点个数

2 正向删除位置 = 节点个数 - 倒数删除位置

3 正向遍历删除位置并删除节点。

学习后的见解

依旧是双指针方法,只能说真的妙,我太笨了根本想不出来

1 分别定义一个双指针和慢指针节点,都指向head。

2 快指针正向移动n个位置,此时若快慢指针同步移动,直到快指针指向节点尾部,则慢指针刚好位于要被删除的节点位置。

3 上述慢指针如果直接删除本身则无法将链表链接起来,所以需要慢指针指向要被删除的节点前一位,快指针正向移动n个位置后再往后移动一个位置。

4 然后再快慢指针所处位置的基础上同步后移,直到快指针指向尾部,此时慢指针正好处于被删除节点前一位。

5 慢指针指向下一位的下一位,并且删除下一位。

6 返回删除后链表头结点。

代码

暴力解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int node_count = 0;
        ListNode* dummy_head =new ListNode();
        dummy_head->next = head;
        ListNode* curr = dummy_head;
        while(curr->next!=nullptr){
            node_count++;
            curr=curr->next;
        }
        int delet_index = node_count - n;
        curr = dummy_head;
        while(delet_index --){
            curr=curr->next;            
        }
        ListNode* tmp  = curr->next;
        curr->next = curr->next->next;
        delete tmp;
        tmp = nullptr;
        return dummy_head->next;
    }
};

双指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int slow_index = 0;
        int fast_index = 0;
        ListNode* dummy_head = new ListNode();
        dummy_head->next = head;
        ListNode* slow_node = dummy_head;
        ListNode* fast_node = dummy_head;
        while(n--&&fast_node!=nullptr){
            fast_node = fast_node->next;
        }
        fast_node = fast_node->next; //因为 slownode需要指向被删除节点的前一个位置
        while(fast_node!=nullptr){
            //同步移动
            fast_node = fast_node->next;
            slow_node = slow_node->next;
        }
        ListNode* tmp = slow_node->next;
        slow_node->next = slow_node->next->next;
        delete tmp;
        tmp = nullptr;
        return dummy_head->next;
    }
};

总结

思路真很清晰明了,但是自己真的无法想出来。

面试题 02.07. 链表相交

讲解链接

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 当两者地址不相等的时候就说明找到相交点前面了。

3 上述思想是错误的,因为如果链表有合并的,那么反转后,另外一条链表的值也会被改。所以此方法不合适。

学习后的见解

1 计算出两个链表长度

2 数据与尾部对其

3 两者同时往后移动

4 当两者地址相等时退出,返回交点

5 遍历至尾部地址都没有相等则说明没交点,返回null

代码

/**
 * 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) {
        //思路,计算出两个链表长度
        //数据与尾部对其
        //两者同时往后移动
        //当两者地址相等时退出,返回交点
        //遍历至尾部地址都没有相等则说明没交点,返回null;
        //求出链表A长度
        int length_A = 0;
        ListNode* currA = headA;
        int length_B = 0;
        ListNode* currB = headB;
        while(currA!=nullptr||currB!=nullptr){
            if(currA!=nullptr){
            currA = currA->next;
            length_A++;
            }
            if(currB!=nullptr){
            currB = currB->next;
            length_B++;
            }
        }
        //求出长度差
        int delta_length = fabs(length_A - length_B);
        currA = headA;
        currB = headB;
        //谁长移动谁
        while(delta_length --){
            if(length_A>length_B){
                currA = currA->next;
            }else{
                currB = currB->next;
            }
        }
        //此时两者位置已经对齐,找出地址相等的节点即可
        while(currA!=nullptr){
            if(currA == currB){
                return currA;
            }
            currA = currA->next;
            currB = currB->next;
        }
        return nullptr;
    }
};

总结

最重要的一点就是要把数据位置对其,然后同步往后移动就好。

142.环形链表II

讲解链接

https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

自我思考

看到题脑子里出现的想法是用一个map把链表往后移动的值和地址记录起来,当后面再次遇到相同的值时再去查对于map的地址和当前地址是否一致,是就找到了环形链表,否则就没有。代码最终没有实现。

学习后的见解

只能说这种方法我绝对想不到。时间不够,待二刷时在补齐思路。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
    //双指针法
    ListNode* slow_node = head; //慢指针
    ListNode* fast_node = head; //快指针
    //如果链表没环,则快指针先到尾部
    while(fast_node!=nullptr&&fast_node->next!=nullptr){  
        slow_node = slow_node->next; //慢指针一次移动一个
        fast_node = fast_node->next->next;  //快指针一次移动两个     
        if(slow_node == fast_node){//有环必相遇
            //公式推导出这遍历方式当两个指针相等时便是环出口
            //x = (n-1)(y+z) +z
            //x = z
            ListNode* meet_node_index_A = head;
            ListNode* meet_node_index_B = fast_node;
            while(meet_node_index_A!=meet_node_index_B){
                meet_node_index_A= meet_node_index_A->next;
                meet_node_index_B = meet_node_index_B->next;
            }
            return meet_node_index_A;
        }
    }
    return nullptr;
    }
};

总结

这个题我没有太多看法,只能说不看不知道,看了就和小学题一样。但问题就在如何想到这一步无解,前辈的智慧还是很厉害的。

链表学习总结

刷了大概两天吧。

1 链表:单链表就是由数据和下一个数据的地址构成;双链表是由上一个数据地址,当前数据以及下一个数据地址组成。

2 链表设计:数据插入,删除,获取。

3 双指针方法:好方法但是不看答案就不会用。

4 虚拟头结点:好东西,省事儿。

相关文章
|
4天前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
15天前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
9 2
|
25天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
23 1
|
25天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
26 1
|
7天前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
11天前
|
存储 SQL 算法
|
25天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
21 0
|
25天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
19 0
|
1月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
11天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表