IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 代码随想录4——链表: 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07链表相交、142.环形链表II -> 正文阅读

[数据结构与算法]代码随想录4——链表: 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07链表相交、142.环形链表II

1.24两两交换链表中的节点

参考:代码随想录24两两交换链表中的节点

1.1.题目

在这里插入图片描述

1.2.思路

在这里插入图片描述在这里插入图片描述

实际上,仔细看上面的图之后还是得到了链表原来那个非常重要的性质:即操作当前节点,一定要通过上一个节点进行访问,因为需要修改上一个节点的next指针新的指向。因此本题虽然是交换相邻的两个节点BC,但是始终会从B的上一个节点A开始操作,即虽然是只交换两个节点,但是操作的时候始终是在操作3个节点,就是因为对链表结构进行修改之后,需要更新其上一个节点的next指针,因此一直需要从A节点开始操作。

比如上面的最后一个图,当交换完1和2之后,cur指向了1的位置,但是实际上下面我们是要交换3和4,此时再次使用原来的套路,1指向4,4指向3,3再指向4后面的那个元素,可见此时仍然是成立的。

1.3.代码实现

1.3.1.对next指针的理解

今天发现在代码编程中对next理解的还是不清晰,有的时候把他认为是当前节点的next指针变量,有的时候又把它理解成当前节点的下一个节点。显然这两种理解都是正确的,但是不同的场景下需要使用切换不同的理解方式,显然很麻烦。比如cur->next = tmp,这个就把next理解成当前节点的指针变量;如果是cur->next->val = 1,这又要把next理解成当前节点的下一个节点。这样切换很难受。

实际上,只需要把next理解成从节点出来的、指向下一个节点的箭头即可。这样理解永远不会出错,而不用区分他到底是指针变量还是指向的下一个节点。所以后面统一记为next箭头

更新:评论中有人对next指针进行了评价,这促使我对next指针又得到了新的理解。

上面自己说对next指针有两种理解,实际上本质原因就在于next指针是归属于两个节点的,它是链接两个节点的桥梁。对于前一个节点来说,next指针就是它的成员变量,此时它就是一个指针变量,比如cur->next = tmp就是在修改这个变量的值。而对于后一个节点来说,上一个节点的next指向的就是当前这个节点的内存地址,所以如果是cur->next->val = 1,那么此时上一个节点的next就相当于是当前节点,此时next就是指针指向的节点。因此是next指针对前后两个节点的联系,导致了它可以有两种不同的理解。

如果统一把next理解成从当前节点出来的、指向下一个节点的箭头:对于cur->next = tmp,就是修改当前节点的箭头指向的方向,让它指向tmp节点; 对于cur->next->val = 1,就是在访问当前节点的箭头指向的节点的值。

1.3.2.编程中要备份哪些节点的指针?

其实很简单,只要是破坏了链表的索引结构,那么都需要备份节点的指针。什么时候会破坏链表的索引结构呢?其实就是修改next箭头的时候。

因此总结为:修改了某个节点的next箭头,此时该节点的下一个节点索引丢失,因此要备份该节点的下一个节点

1.3.3.代码实现

class Solution
{
public:
    struct ListNode
    {
        int val;
        ListNode* next;
        ListNode(int x): val(x), next(nullptr){}
        ListNode(int x, ListNode* ptr): val(x), next(ptr){}
    };

    ListNode *swapPairs(ListNode *head)
    {
        ListNode* dummy_node = new ListNode(0);
        dummy_node->next = head;
        // 链表举例: [cur, 1, 2, 3, 4]
        // 索引位置: [cur, 1, 2, 3, 4]
        ListNode* cur = dummy_node;  // 从虚拟头节点0开始
        // 要交换的是第1和2个节点,因此他们不能是空
        while(cur->next != nullptr && cur->next->next != nullptr)
        {
            // 关于要备份哪些节点,实际上可以先编程后面,发现哪里缺了再在这里备份
            ListNode* tmp1 = cur->next;
            ListNode* tmp3 = cur->next->next->next;

            // 步骤1:cur的箭头指向第2个节点,由于cur的箭头被修改,因此需要备份它原来箭头指向的节点,即tmp1
            cur->next = cur->next->next;
            // 步骤2:第2个节点的箭头指向第1个节点,由于第2个节点的箭头被修改,因此要备份它原来箭头指向的节点,即tmp3
            cur->next->next = tmp1;
            // 步骤3:第1个节点的箭头指向第3个节点
            cur->next->next->next = tmp3;

            cur = cur->next->next;   // 最后,cur跳两个位置,交换下两个节点
        }
        return dummy_node->next;  // 返回交换后的链表的头指针
    }
};

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

参考:代码随想录19删除链表的倒数第N个节点

2.1.题目

在这里插入图片描述

2.2.思路

注意这里是求倒数第n个节点,一个比较简单的思路是把原来的链表先遍历一遍,求出来它一共有多少个节点N,然后再把总结点数N减去n,就得到了正向数要删除的是第几个节点N-n。这样再次遍历列表到第N-n个节点,对这个节点进行删除。但是很显然这样两个for循环遍历,复杂度是n^2。

另外一个很好的解法是使用双指针,一个fast和一个slow指针都指向虚拟头节点,然后fast指针先向后移动n,然后fast和slow一起向后移动,直到fast移动到最后一个节点,此时slow也就移动到了要被删除的节点。

class Solution
{
public:
    struct ListNode
    {
        int val;
        ListNode* next;
        ListNode(int x): val(x), next(nullptr){}
        ListNode(int x, ListNode* ptr): val(x), next(ptr){}
    };

    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode* dummy_node = new ListNode(0, head);

        ListNode* fast = dummy_node;
        ListNode* slow = dummy_node;
        while(n-- && fast->next != nullptr)
        {
            fast = fast->next;
        }
        // 至此fast->next就是第n个节点
        while(fast->next != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        // 至此fast指向最后一个节点,slow的下一个节点就是倒数第n个节点,就是要被删除的节点

        ListNode* tmp = slow->next;   
        // 这里修改了next箭头的指向,因此上面要备份原来的next箭头指向的节点
        slow->next = slow->next->next;
        delete tmp;

        return dummy_node->next;
    }
};

3.面试题02.07链表相交

参考:代码随想录面试题0207链表相交

3.1.题目

在这里插入图片描述

3.2.解答

其实链表相交很简单,一定满足是在后面相交的。所以只需要把两个链表在尾部对齐,然后从短的链表的开头开始遍历,比较两个链表对应节点的指针是否相等, 如果相等就找到了相交点。

class Solution
{
public:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(nullptr) {}
    };


    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int len_a = 0;
        int len_b = 0;
        ListNode* cur_a = headA;
        ListNode* cur_b = headB;

        // 查询AB两个链表的总长度
        while(cur_a != nullptr)
        {
            len_a++;
            cur_a = cur_a->next;
        }
        while(cur_b != nullptr)
        {
            len_b++;
            cur_b = cur_b->next;
        }

        // 把两个指针恢复到头指针
        cur_a = headA;
        cur_b = headB;

        int offset = len_a - len_b;
        if(offset > 0)
        {
            while(offset--)
            {
                cur_a = cur_a->next;
            }
        }
        else
        {
            offset = -offset;
            while(offset--)
            {
                cur_b = cur_b->next;
            }
        }

        while(cur_a != nullptr)
        {
            if(cur_a == cur_b)
            {
                return cur_b;
            }
            else
            {
                cur_a = cur_a->next;
                cur_b = cur_b->next;
            }
        }

        return nullptr;
    }
};

4.142.环形链表II

参考:代码随想录142环形链表II

4.1.题目

在这里插入图片描述

4.2.思路

整体思路都是参考代码随想录中的讲解,详细内容去看讲解吧,本题还是比较复杂的,从判断是否有环,到计算环的第一个入口点,都有很多分析。

注意在其中有几个问题:

  1. 为什么fast指针走两步,slow指针走一步,如果有环的话他们一定会相遇呢

其实这个问题根据讲解分为两步:
(1)如果有环,那么一定是fast先进入环。这个很容易理解,因为fast走的快嘛。
(2)当slow指针进入环之后,此时只要fast指针没有立即和slow指针相遇,那么不论fast指针在什么地方,都可以把slow指针认为是在前面运动的指针,然后fast指针就在追slow指针。fast指针每次都比slow指针多走一步,因此fast指针在一步一步的追slow指针,他们之间的距离就是一步一步的在减小,因此他们一定会相遇,最多追赶的次数也就是y+z-1次,其中y+z是环的节点个数。

为什么最多的追赶次数是y+z-1?因为slow刚进入环的时候,如果fast此时也在环的入口点,此时他们直接就相遇了,不用追赶,追赶次数就是0次。只要fast不在环的入口点,按照上面的理解,此时一律都认为slow指针在前面,fast指针在后面追slow指针。那么追的最大次数也就是fast指针恰好在slow指针的下一个节点上,然后fast指针就要比slow指针多走y+z-1次才能追上slow指针,也就是就差一步就追完一圈,这差的一步就是刚开始的时候fast指针在slow指针的下一个节点导致的。

  1. 计算入口节点的时候,为什么slow指针在环内走过的长度只可能是y,而不是n*(y+z) + y呢?即slow指针不可能走完一圈

其实这个问题在上面的问题中已经得到了解答,就是如果slow在刚进入环的时候如果和fast没有相遇,那么fast就要一步一步的去追slow,而且此时追slow需要的步骤次数最多就是y+z-1次,即不会走完一个环,所以说slow指针被fast指针追上之前,在环内肯定不可能走完一圈,最大的长度也就是走y+z-1步,也就是从环的入口开始,走到环的入口的前一个点,此时恰好被fast追上。实际上,这种情况对应的是在slow刚进入环的时候,fast恰好在环的入口的下一个节点上,然后fast就需要追y+z-1步才能追上slow指针。

  1. 最后计算相遇节点的时候,得到的公式是x = (n-1)*(y+z) + zn=1x=z,为什么n>1时结果和n=1时结果一样

其实从分析这个公式就可以知道,即一个指针从起点开始,另一个指针从相遇点开始,每次每人各走一步,最后走完x步以后他们一定会在环的起点相遇。此时如果n>1,就相当于另一个指针在环中等了从head出发的第一个指针很久,在环里绕了很多次了。但是最后的结果他们还是会在环的入口处相遇的。

class Solution
{
public:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };

    ListNode *detectCycle(ListNode *head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        // 注意这里只判断到fast->next即可,不需要判断到fast->next->next
        while(fast != nullptr && fast->next != nullptr)
        {
            // 这里一定要先移动再判断,而不能上来就判断是否相等,因为一开始他俩都是head,肯定是相等的
            fast = fast->next->next;
            slow = slow->next;
            // 找到了环的入口点
            if(fast == slow)
            {
                // 让一个新的指针从head出发,然后每次走一步,最终会和slow指针在环的入口点相遇
                ListNode* new_slow = head;
                while(new_slow != slow)
                {
                    new_slow = new_slow->next;
                    slow = slow->next;
                }
                return new_slow;
            }
        }
        return nullptr;
    }
};
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-25 23:20:35  更:2022-09-25 23:22:18 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/28 18:53:56-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码