单链表算法题
单链表算法题
移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
首先题干要求是干什么？
由示例一可以看到删除链表中所有满足 Node.val == val 的节点，然后变成一个新的节点
其次有什么假设？
思路一：遍历链表，在原链表执行删除指定节点的操作
思路二：创建新链表，将原链表中值不为val的节点尾插到新链表中
再往后每一步的目的是什么？
思路二：
- 创建三个指针，目的是进行对链表的遍历
- pcur的遍历，遇到满足的节点不会停止，目的是不缺不漏
- newHead的创建是为了和符合题意“返回新的头节点“，newTail是进行尾插，尾插的位置是newTail->next
代码如下：
为什么会有这样的假设，如果这个假设不成立，能举出什么反例？
-
单链表的尾插操作我们可以知道，很重要的一点是要判断链表是否为空，首先先判断，如果为空，创建一个链表，让newHead=newTail=pcur,如果不为空，就进行尾插操作
-
当遍历完原链表之后，我们需要判断尾节点的后面，如果说不去判断，反例就是val=6,有一个链表的元素是[1,2,3,4,5,6],如果把6去掉，那么newTail的指向就是成了问题，所以我们要让newTail->next=NULL
-
还要判断链表是否存在，如果说[7,7,7,7,7],但是val=7,这时候就没有链表存在，所以要去判断newTail是否存在
有哪些值得借鉴的地方呢？
- 在这道OJ题目中，比如说遇到名字比较长的结构体啥的，可以用typedef重命名
- OJ代码有bug怎么办？VS调试技能⽤起来
1）将OJ代码复制粘贴到vs上
2）创建测试⽅法，调⽤本次要调试的⽬标⽅法
3）利⽤vs调试⼯具排查代码问题
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 next=NULL;
//大小链表首尾相连
lessTail->next=greaterHead->next;
ListNode*ret=lessHead->next;
free(lessHead);
free(greaterHead);
return ret;
}
};
有什么值得借鉴的地方？
-
在开辟新的链表的空间的时候：
lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));
好处是不用判断链表是否为空，使代码不再变得冗余
-
带头或不带头的链表
在带头链表中，除了头节点，其他节点都存储着有效数据，head占位子，也可以理解为“哨兵位”
链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例
1->2->2->1 返回：true
首先在宏观上在干什么？
提到“回文”，可能会想到回文数字，回文字符串，回文亦称为轴对称
其次有什么假设？
创建新的数组，遍历原链表，将链表节点中的值放到数组中，在数组中判断是否为回文序列
再往后每一步目的是什么？
因为题干中说，保证链表长度小于等于900，说明数组的大小可以去确定
代码如下：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool chkPalindrome(ListNode* A) { int arr[900]={0}; ListNode*pcur=A; int i=0; //将链表中的元素遍历到数组中，因为数组可以两头处理，单链表不行 while(pcur) { arr[i++]=pcur->val; pcur=pcur->next; } //i即节点的个数 //找中间节点，判断是否为回文结构 int left=0; int right=i-1; while(leftnext) { slow=slow->next; fast=fast->next->next; } return slow; } ListNode*reverseList(ListNode*phead) { ListNode*n1,*n2,*n3; n1=NULL,n2=phead,n3=n2->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; } bool chkPalindrome(ListNode* A) { //1.找中间节点 ListNode*mid=findMidNode(A); //2.根据中间节点反转后面的链表 ListNode*right=reverseList(mid); //3.从原链表和反转后的链表比较节点的值 ListNode*left=A; while(right) { if(left->val!=right->val) { return false; } left=left->next; right=right->next; } return true; } };
此时要注意的是while循环中right是另一个起点。
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
- intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
- listA - 第一个链表
- listB - 第二个链表
- skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
- skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
相交的概念是由哪个问题衍生出来的？
这里的相交和数学里面的相交不太一样。
相交在链表中的含义是：两个链表从头开始遍历，尾节点一定是同一节点
为什么会有这样的假设呢？
有哪些假设？
1 .如何判断链表是否相交
- 遍历两个链表，若尾节点相同则链表一定相同
2 .找相交链表的起始节点
这时候在遍历链表的时候会出现两种情况：
1)两个链表的节点个数相同
2）两个链表的节点个数不同
1）找两个链表的节点上差值
2）长链表先走差值步
3）两个链表开始遍历，比较是否为同一节点
代码如下：
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 104]
- -105 next;
int n=3; //fast每次⾛三步
while(n--)
{
if(fast->next)
fast = fast->next;
else
return false;
}
if(slow == fast)
{
return true;
}
}
return false;
}
💡 提⽰ 虽然已经证明了快指针不论⾛多少步都可以满⾜在带环链表中相遇，但是在编写代码的时候 会有额外的步骤引⼊，涉及到快慢指针的算法题中通常习惯使⽤慢指针⾛⼀步快指针⾛两步 的⽅式。
环形链表2
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围 [0, 104] 内
- -105 y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
提示：
- 0
- 遍历两个链表，若尾节点相同则链表一定相同
-
-
