单链表OJ--8.相交链表

8.相交链表 160. 相交链表 - 力扣（LeetCode） /* 解题思路： 此题可以先计算出两个链表的长度，让长的链表先走相差的长度，然后两个链表同时走，直到遇到相同的节点，即为第一个公共节点 */ struct ListNode ListNode *headB) { int lenA = 0, lenB = 0; struct ListNode* curA = headA, *curB = headB; //计算链表长度 shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } //让长链表先走几步 while(gap--){ longList = longList->next; } //两个链表同时走，直到遇到相同的节点 while(longList

《手撕链表题系列-8》相交链表

前言 本系列主要讲解链表的经典题 注：划重点！！必考~ 链表分割 力扣链接：160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com) 题目描述： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。 如果两个链表没有交点，返回 null 。 同时如果两链表末尾结点地址不同，则表示没有两链表没有相交 对长链表指针先走长度差个结点，再两个指针同时遍历 当两个结点指针相遇时即为相交节点 参考代码： /** * Definition for singly-linked cur1->next; } while(cur2->next) { len2++; cur2=cur2->next; } //各链表尾节点不相等则两链表不相交

算法练习(8)-判断单链表是否回文链表

回文单链表跟这个类似，比如: 0-1-2-1-0或0-1-1-0，很容易发现规律：可以找到一个对称轴，将链表分为前后二段，并且前后对折起来，完全重合。 public LinkNode(int val, LinkNode next) { 6 this.val = val; 7 this.next = next; 8 3 * @blog http://yjmyzz.cnblogs.com 菩提树下的杨过 4 */ 5 public class LinkNodeUtils { 6 7 /** 8 ，逐一加入堆栈，由于堆栈先进后出，这样相当于把链表翻过来了，然后跟原链表逐一对比，即：正向与反向，检查所有元素是否重合。 不过别忘了：这样会破坏原链表，所以在检查结束后，记得将后半段，再翻转回来，跟前半段续接上，还原整个链表。

【链表问题】打卡8：复制含有随机指针节点的链表

【要求】 如果链表的长度为 N, 时间复杂度达到 O(N)。 例如对于链表 1->2->3->null。创建副节点 1', 2', 3'。然后用哈希表关联起来： key value 1 1' 2 2' 3 3' 之后在把所有副节点连接成一个链表。 = null) { 6 map.put(cur, new Node1(cur.value)); 7 cur = cur.next; 8 } 9 //把副节点连接起来 例如，对于链表 1->2->3->null。首先生成副节点 1', 2', 3。然后把副节点插入到原节点的相邻位置，即把原链表变成 1->1'->2->2'->3->3'->null。 = null) { 8 next = cur.next; 9 Node1 temp = new Node1(cur.value);//复制节点 10 temp.next

leetcode刷题（8）——删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。 现有一个链表 – head = [4,5,1,9]，它可以表示为: 示例 1: 输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点 ，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = [4,5,1,9], node = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -

【初阶数据结构】链表经典OJ（8道）

输入一个链表，输出该链表中倒数第k个结点。OJ链接 对于单向链表，我们无法直接获取链表的尾节点，同时本题还要求返回倒数第几个节点，这就要求我们能够判断相对位置。 因此在比较之前，我们需要先循环遍历两个链表，得出两个链表的长度，让长的链表先走两个链表长度差步，这样两个链表到相交节点前长度相等。 这样后，我们就可以直接进行循环遍历比较了。 给定一个链表，判断链表中是否有环。 ，没有返回空 } } return NULL ;//不存在环 } 8.给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点 本题的主要的难点在于如何实现新链表的random的指针指向关系与原链表相似，需要注意的是， 新链表的random指向不是指向原链表中的节点，而是新的节点，得到的新链表与原链表出指针指向的空间不同，其他的

链表——新建链表

#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) {

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

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

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

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

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

，而且链表的空间是存储在堆上面的，可以动态分配，释放。 链表的每个节点就是一个结构体变量，节点里有一个或者两个指针，可以保存上一个节点和下一个节点的地址，方便遍历链表，删除、插入节点时定位位置。 2. 实现的功能如下: 初始化链表头 插入节点的函数(链表任意位置插入，链表尾插入) 删除节点的函数（链表任意位置删除、链表尾删除） 遍历链表，输出链表里的所有信息 #include <stdio.h> #include 找到链表尾 while(next_p! 找到链表尾 if(head!

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 的链表节点，返回 反转后的链表 。

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

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

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

题目链接 反转链表 方法一：迭代 循环从第二个节点开始。 首先判断若没节点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

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

leetcode链表之反转链表

序 本文主要记录一下leetcode链表之反转链表 题目 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

清空链表和销毁链表

清空链表和销毁链表的区别： 清空链表：将所有除头节点以外的存放有数据的节点释放掉 销毁链表：将包括头结点在内的所有节点释放掉 注意：当清空所有有数据的节点，并且释放头结点后，该链表就无法再通过头结点创建 ，访问，插入，删除节点，因此相当于销毁了此链表 清空链表 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef struct LinkNode { int num; LinkNode* next; }Lk, * lk; //有头链表的初始化 lk initLinkNode() { //创建头结点 lk 注意：清空链表后，链表还是可以继续使用 ? 画图说明： ? 注意销毁链表后，就不能对链表进行任何操作，否则为访问权限冲突，因为头结点指向的内存的操作权限已经归还给了操作系统 ? 画图说明： ?

Java链表——创建链表对象

链表是一种简单的数据结构。由两部分构成，数值部分和指针部分。 前一部分用来存储数据，后一部分存放的是下一个数据的地址，用于指向下一个数据。形成一个链状的结构。 我们在包里新建一个类，在需要使用链表时，用此类创建链表对象即可。链表是由一个个节点构成的，我们建立一个节点类，目的是通过此类能够创建一个链表节点。然后就能以他为起点，插入其他的节点形成链，成为链表。 链表的一个节点需要具备以下要素： 值域 指针 构造函数 调用私有变量的函数 public class ListNode { private int val; private ListNode next 这样我们就可以在其他的类中建立链表对象了，像这样； ListNode firstNode = new ListNode(1); ListNode secondNode = new ListNode(2) 链表的插入操作 发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/141065.html原文链接：https://javaforall.cn