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 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 随想录一刷Day04——链表 -> 正文阅读

[数据结构与算法]随想录一刷Day04——链表

Day04_链表

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

24. 两两交换链表中的节点
思路:

按照下如图模拟
在这里插入图片描述

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* _dummyHead = new ListNode(0);
        _dummyHead->next = head;
        ListNode* cur = _dummyHead;
        while (cur->next && cur->next->next) {
            ListNode* tmp = cur->next; // 记录节点1
            ListNode* tmp_next_pair = cur->next->next->next; // 记录下一对节点的起点
            cur->next = cur->next->next; // 步骤一
            cur->next->next = tmp; // 步骤二
            tmp->next = tmp_next_pair; // 步骤三
            cur = cur->next->next; // 虚拟节点移动到下对节点的正确位置
        }
        return _dummyHead->next;
    }
};

6. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点
思路:

本来想两次遍历,看到卡哥的双指针,直呼挺妙,虽然复杂度也是 O ( n ) O(n) O(n)
利用双指针间格n个位置,就可以在fast指针移动到链表结尾时,slow指针停在要删除的节点前。

在这里插入图片描述

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* _dummyHead = new ListNode(0);
        _dummyHead->next = head;
        ListNode* fast_index = _dummyHead;
        ListNode* slow_index = _dummyHead;
        while(n-- && fast_index) {
            fast_index = fast_index->next;
        }
        while(fast_index->next) {
            fast_index = fast_index->next;
            slow_index = slow_index->next;
        }
        slow_index->next = slow_index->next->next;
        return _dummyHead->next;
    }
};

7. 链表相交

面试题 02.07. 链表相交
思路:

又不是自己想的,呜呜呜
显然不能是利用两个节点的值相等作为判断依据,要判断指针地址一致才行。如何让两个节点能够在相交处相遇呢?就让两个链表从头部对齐变为尾部对齐,接下来一起以相同的速度往后遍历,一定会在相交的点处相遇。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A_pos = headA;
        ListNode* B_pos = headB;
        int lenA = 0, lenB = 0;
        while(A_pos) { // 获取A链表的长度
            lenA++;
            A_pos = A_pos->next;
        }
        while(B_pos) { // 获取B链表的长度
            lenB++;
            B_pos = B_pos->next;
        }

        int delta_len = lenA - lenB; // 默认链表A长
        A_pos = headA;
        B_pos = headB;
        if (delta_len < 0) { // 调整为A链表为长链表
            swap(lenA, lenB);
            swap(A_pos, B_pos);
            delta_len = abs(delta_len);
        }
        
        while(delta_len--) { // 将A、B链表尾部对齐
            A_pos = A_pos->next;
        }

        while (A_pos && A_pos != B_pos) { // 同时遍历A、B链表,找到相交节点
            A_pos = A_pos->next;
            B_pos = B_pos->next;
        }

        return A_pos;
    }
};

8. 环形链表 II

142. 环形链表 II
思路:

实用两个指针,一快一慢,快指针一次走两步,慢指针一次走一步。如果两个指针相交,则有环。然后快指针在交点处,慢指针在起点处,以步长为1运动,直到相遇点,为环的交点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast_index = head;
        ListNode* slow_index = head;
        while(fast_index && slow_index) {
            fast_index = fast_index->next;
            slow_index = slow_index->next;
            if (fast_index == NULL || slow_index == NULL) return NULL;
            fast_index = fast_index->next;
            if (fast_index == slow_index) break;
        }
        if (fast_index == NULL || slow_index ==NULL) return NULL;
        // cout << "here" << endl;
        slow_index = head;
        while (fast_index != slow_index) {
            fast_index = fast_index->next;
            slow_index = slow_index->next;
        }
        return fast_index;
    }
};
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-25 23:20:35  更:2022-09-25 23:22:30 
 
开发: 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 19:17:50-

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