LeetCode之链表(10)

LeetCode之链表(10) 0.说在前面 1.反转链表 2.两两交换节点 3.环形链表 4.环形链表II 5.作者的话 0.说在前面 今天有点闲，就来连刷几道题，下次不这样干了，有点hold不住，建议以后保持平衡刷题规律 下面列出今天刷的题的名字： 反转链表 两两交换链表中的节点 环形链表 环形链表II 四道题。。。 是不是有点崩溃~~其实只有两道，第一道很easy的一道，后面两个环形链表与环形链表II合并为一个，总共就只有两个，不多吧，哈哈~开始刷题！ 1.反转链表 【问题】 反转一个单链表。 【问题】 给定一个链表，判断链表中是否有环。 II 【问题】 给定一个链表，返回链表开始入环的第一个节点。

单链表OJ题——10.环形链表2

10.环形链表2 142. 环形链表 II - 力扣（LeetCode） /* 解题思路： 如果链表存在环，则fast和slow会在环内相遇，定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow

算法练习(10) - 反转链表(O(n))

思路 : 首先是1. 头删 ,头删之前需要把头结点给到结果指针,这样才能头插 ,于是 2. 缓存头删指针 但是返回指针如果指引到最新的头插节点,那么上次头插的结果会丢失,所以需要先将返回指针指向的节点引用缓存起来 ,于是 3. 缓存结果指针 ,最后 4. 头插 将结果指针指向的最新节点 头插到老的 返回头结点上;

1-10 链表去重 (20 分)

本文链接：https://blog.csdn.net/shiliang97/article/details/100149932 1-10 链表去重 (20 分) 给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉 同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。 输入格式： 输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤10​5​​，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。 随后 N 行，每行按以下格式描述一个结点： 地址 键值 下一个结点 其中地址是该结点的地址，键值是绝对值不超过10​4​​的整数，下一个结点是下个结点的地址。 题目大意：给一个链表，去重（去掉值或者绝对值相等的），先输出删除后的链表，再输出删除了的链表。 分析：用结构体数组存储这个链表，大小为maxn = 100000，node[i]表示地址为i的结点。

] 2022-03-10 86. 分隔链表

前言 链表的特点 适合 插入和 删除 一个元素，不需要整体移动。 分隔链表 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔 你应当 保留 两个分区中每个节点的初始相对位置。 pcur := head ppre := ptail //04 链表的遍历 for pcur ! ptail = pcur ppre = pcur pcur = pcur.Next //对同一个位置 不需要翻转 } else { //一个元素把链表 分割成为2部分，全部大于 ppre.Next = pcur.Next //删除 pcur.Next = ptail.Next //链表尾节点插入 ptail.Next = pcur //链表尾节点插入

数据仓库(10)数仓拉链表开发实例

拉链表是数据仓库中特别重要的一种方式，它可以保留数据历史变化的过程，这里分享一下拉链表具体的开发过程。 维护历史状态，以及最新状态数据的一种表，拉链表根据拉链粒度的不同，实际上相当于快照，只不过做了优化，去除了一部分不变的记录，通过拉链表可以很方便的还原出拉链时点的客户记录。 这里的拉链表，我们做到天粒度的。 架构数据仓库(05)数仓Kimball与Inmon架构的对比数据仓库(06)数仓分层设计数据仓库(07)数仓规范设计数据仓库(08)数仓事实表和维度表技术 数据仓库(09)数仓缓慢变化维度数据的处理数据仓库(10 )数仓拉链表开发实例数据仓库(11)什么是大数据治理，数据治理的范围是哪些数据仓库(12)数据治理之数仓数据管理实践心得数据仓库(13)大数据数仓经典最值得阅读书籍推荐

【链表问题】打卡10：将搜索二叉树转换成双向链表

在结构上，两种结构有相似性，现有一棵搜索二叉树，请将其转为成一个有序的双向链表。 这棵二查搜索树转换后的双向链表从头到尾依次是 1～9。 采用中序遍历的方法，把二叉树的节点全部放进队列，之后在逐一弹出来连接成双向链表。 queue.isEmpty()) { 10 cur = queue.poll(); 11 pre.right = cur; 12 cur.left = pre; = null) { 10 leftE.right = head; 11 head.left = leftE; 12 head.right = rightB; 13

PTA 带头结点的单链表就地逆置（10 分）

L是一个带头结点的单链表，函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置，如原单链表元素依次为1,2,3,4，则逆置后为4,3,2,1。 函数接口定义： void ListReverse_L(LinkList &L); 其中 L 是一个带头结点的单链表。 L)exit(OVERFLOW); L->next=NULL; //先建立一个带头结点的单链表 rearPtr=L; //初始时头结点为尾节点,rearPtr curPtr; } return OK; } void ListReverse_L(LinkList &L); void ListPrint_L(LinkList &L){ //输出单链表 } ListReverse_L(L); ListPrint_L(L); return 0; } /* 请在这里填写答案 */ 输入格式： 第一行输入一个整数n，表示单链表中元素个数

链表——新建链表

#include <stdio.h> #include <stdlib.h> #include <string.h> struct node { int data; struct node *pNext; }; //新建node struct node * create_node(int data) { struct node *p = (struct node *) malloc (sizeof(struct node)); if(NULL == p) {

《链表篇》---相交链表

题目链接 相交链表 方法一：哈希集合 判断两个链表是否相交。使用哈希集合存储链表节点。 创建一个哈希Set集合。先将链表A中的节点放入这个集合中。 再遍历链表B。 pA 从链表 headA 的头部开始遍历，pB 从链表 headB 的头部开始遍历。 如果 pA 到达了链表 headA 的末尾（pA == null），就让它跳到链表 headB 的头部继续遍历。 当 pA 到达链表headA的末尾时，pA 被重置为链表headB的头部，这是为了让 pA 开始遍历链表headB。 类似地，当 pB 到达链表headB的末尾时，pB 被重置为链表headA的头部。 通过这种方式，两个指针在遍历完自己的链表后，会从对方的链表头开始遍历。 由于两个指针都会遍历两个链表的总长度，无论两个链表的长度是否相同，最终两个指针会在相交节点处相遇，或者同时到达链表的末尾（即没有相交节点的情况）。

【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

【Leetcode21】合并两个有序链表 1.链接 合并两个有序链表 2.题目再现 3.三指针尾插法 思路：创建一个新的链表，分别遍历两个链表，小的就尾插到新链表，然后指针向后走一步，直到有一方为空时就结束循环 ；结束循环后，判断哪个链表不为空，把不为空的尾插到新链表中去。 分表遍历两个链表，比较其值，小的尾插到新链表，并向后走一步（如果一样大，那么随便取哪一个都行）； 4.结束循环后，判断哪个链表不为空，尾插到新链表。 【Leetcode160】相交链表 1.链接 相交链表 2.题目再现 3.解法 1.先分别遍历两个链表，记录下两个链表的长度； 2.如果两个链表尾节点的地址一样，则说明它们相交，否则不相交，（注意是地址不是值 ）； 3.求出两个链表长度的差gap； 4.先让长的链表走差距步gap，短的链表先不动； 5.然后两个链表同时走一步，比较每走一步时两个链表当前节点的地址，如果一样，则说明找到了它们相交的起始位置

【数据结构】线性表 ② ( 链式存储结构 - 链表 | 链表分类 - 单链表 双链表 非循环链表 循环链表 | 链表优缺点 )

一、链式存储结构 - 链表 链式存储结构 就是 链表 LinkedList ; 链式存储结构 ( 链表 ) ： 数据 存储在 节点 中 , 每个节点包含 数据值 和 指向下一个节点的指针 ; 通过节点之间的指针关系 Object data; // 指向下一个节点 Node next; // 指向上一个节点 Node last; } 二、链表分类 - 单链表 / 双链表 / 非循环链表 / 循环链表 单链表 与 双链表 : 单链表 : 上述链表是 单链表 , 单链表 只有一个指针 指向下一个节点 ; 双链表 : 还有一种链表是 双链表 , 双链表 有两个指针 , 一个指向下一个节点 , 一个指向上一个节点 ; 循环链表 : 如果 最后一个节点的指针 指向 第一个节点 , 那么这个链表就是循环链表 ; 链表可以分为以下四类 : 单链表 单循环链表 双链表 双循环链表 三、链表优缺点 链表 LinkedList 链表 LinkedList 缺点： 查询 性能低 ： 如果要访问 链表中 指定位置的元素 , 需要从头节点开始遍历到目标位置 , 时间复杂度为O(n)。

C语言-链表(单向链表、双向链表)

链表的每个节点就是一个结构体变量，节点里有一个或者两个指针，可以保存上一个节点和下一个节点的地址，方便遍历链表，删除、插入节点时定位位置。 2. 实现的功能如下: 初始化链表头 插入节点的函数(链表任意位置插入，链表尾插入) 删除节点的函数（链表任意位置删除、链表尾删除） 遍历链表，输出链表里的所有信息 #include <stdio.h> #include 在链表尾插入数据 list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add 在链表尾插入数据 list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add 添加链表节点*/ list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add

Leetcode:相交链表，环形链表，环形链表||

相交链表 题目描述 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 思路： 先分别遍历两个链表，得出两个链表的节点个数和两个链表节点数的差，再创建两个指针指向两个链表，让节点数较多的链表的指针先遍历这个差值的节点数，然后两个指针再同时遍历，当两个指针指向的节点的地址相同时 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

【Leetcode】重排链表、旋转链表、反转链表||

重排链表 题目描述 给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln-1 提示： 链表的长度范围为 [1, 5 * 104] 1 <= node.val <= 1000 方法一： 将链表的每一个节点存在数组里，然后用下标访问的方式，交叉连接。 ，然后将中点后的链表翻转成一个新的链表，最后将这个新链表和原链表切割掉中间节点之后的链表合并成一个新的链表，合并方式是交叉合并。 题目描述 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

【数据结构】10道经典面试题目带你玩转链表

思路二:双链表遍历尾插法 如图,我们再创建一个单链表newhead,然后创建一个cur指针负责遍历待删链表,再创建一个tail指针负责记录新链表的尾结点: 当cur结点的值不为val时,我们将该结点尾插到新链表的后面 newnode中: 直到将待逆置链表全部尾插到newhead链表中: 这时链表就逆置完毕了,这时返回newhead,即新链表的头即可. 题目详情: 解题思路: 双指针尾插新链表法: 如图,我们创建一个新链表,以及三个指针,分别是cur1,cur2,tail,分别用来遍历链表1,遍历链表2,记录新链表的尾结点. 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

《链表篇》---反转链表

题目链接 反转链表 方法一：迭代 循环从第二个节点开始。 首先判断若没节点head为null 或者 若只有一个节点。head.next = null。则返回head。 接下来 定义一个 cur 节点，指向链表的第二个节点。这个 cur 将用于遍历链表。 将当前 head 节点的 next 设为 null，因为它将成为反转链表的末尾节点。 之后 开始遍历链表并反转指针 1.ListNode curNext = cur.next; 保存cur.next的值，防止丢失。 2.cur.next = head 反转链表。 令cur.next指向前一个节点 3.head = cur 设置反转链表的头结点。 假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？

《链表篇》---回文链表

题目传送门 方法一：将值复制到数组中后用双指针法 思路： 1.将链表的值赋值到顺序表当中。 2.使用双指针法，判断顺序表中的值是否是回文。 left++; right--; } return true; } } 方法二：使用栈 思路： 1.先将链表中的值全部入栈 2.遍历链表，若链表元素与栈顶元素相等，则出栈。 3.栈最后为空，返回true。栈不为空返回false。 反转后半部分链表。 判断是否回文。 恢复链表。 返回结果。 isPalindrome(ListNode head) { if (head == null) { return true; } // 找到前半部分链表的尾节点并反转后半部分链表

Leetcode|找单链表中点+链表反转+链表合并|143. 重排链表

1 寻找单链表中点 + 链表反转 + 链表合并 这道题是道综合题，把三个知识点串起来，非常适合复习链表处理的三个技巧 【思路】：观察发现可以把链表后一半进行反转，然后当成两个链表的合并任务即可 class head) return; // 1.寻找链表中点(快慢指针) auto premid = findmid(head); // 2.链表反转(pre/cur auto l1 = head; auto l2 = premid->next; premid->next = nullptr; // 3.链表合并 (先保存next然后穿针引线) merge(l1, l2); } // 合并链表 void merge(ListNode* l1, ListNode* l2) { while (l1 && l2) { // 先保存两个链表的next auto l1next = l1->next; auto l2next

《链表篇》---环形链表