力扣_初级算法_链表_1~6题
2021-04-22 15:28
标签：防止 要求 需要 val mic 代码 应用 sts from 第1题：删除链表中的节点 题目描述： 举例： 示例 1: 示例 2: 说明: 应用背景（自己琢磨想的）：这个算法比较简单，只是我用的指针个数没有教材上的多。 简化了一下（ 但副作用是没有释放 需要被删除节点的 ） 思路：略。 实现：（C++） /** 第2题：删除链表的倒数第N个节点 题目描述： 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 举例： 示例： 说明： 给定的 n 保证是有效的。 应用背景（自己琢磨想的）：为什么要删倒着数的？可能是为了加点难度。 删除正着数很容易。这道题就想训练一下我们的思维。 思路：可以使用双指针（快慢指针，一个向前走得快，一个向前走得慢。靠它俩之间的“位移”差来判断位置）。也可以用一般思路， 先遍历有多少个节点。用其节点的总数目减去n，就回到正着数的情况。 实现：（C++）我用的一般思路 /** ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 第3题：反转链表 题目描述：反转一个单链表。 举例： 示例: 应用背景（自己琢磨想的）：感觉和数学里面的“对称”、“中心对称”，物理里的“对称性”有共性。 反转链表可以进一步用来判断“回文链表”。也可以进一步延伸到“局部反转”，再进一步扩展到“链表排序”。 思路：巧妙地运用递归函数。（看思路图时，要结合代码来看，清晰一点） PS：思路图纯word文档做，小心酸~~~ 实现：（C++） /** ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 第4题：合并两个有序链表 题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 举例： 示例： 思路：建立一个哑结点（ “节点”和“结点”都可以 ，哑结点就是在链表前面再加一个没有储存信息的结点），然后分别用两个指针( l1和l2 )指向第一个和第二个链表头。 再定义一个指针 pre ，这个指针总是指向，先前移动的指针 l1（或者指针 l2）的前面一位数。 思路图如下： 实现：（ C++ ） /** ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 第5题：回文链表 题目描述： 请判断一个链表是否为回文链表。 举例： 示例 1: 示例 2: /** 给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 举例： /** 力扣_初级算法_链表_1~6题 标签：防止 要求 需要 val mic 代码 应用 sts from 原文地址：https://www.cnblogs.com/Wang-dou-dou/p/13276969.html
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {} //结构体的构造函数，C++中有，C中没有
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) { //传入的是指向被删除元素的指针
node->val=node->next->val; //使得该指针指向节点（非末尾，题目中说的）的数值，变为下一个节点的数值
node->next=node->next->next; //使得该指针指向的节点的指针域改变方向，去指向往后数第二个节点
} //举例： 1->2->3 （要求删除2）。 第一步：1->3->3。 第二步：1->3
};
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {} //结构体的构造函数，C++中有，C中没有
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int i=0,index; //index：作为下标
ListNode *p,*q; //定义两个结构体指针
p=head;
q=head;
while( head ) //遍历一遍链表，看有多少个节点
{
i++;
head=head->next;
}
head=p;
if( n>i||n index=i-n; //顺着数（也就是，正着数的意思）过来的位置的前一位
while( index-1>0 ) //使得q指向被删除节点的前一个节点
{
q=q->next; //经过这整个循环体后，q最终指向被删除节点的前一个节点
index--;
}
if( index==0 ) //如果被删除的节点是表头（链表首部）
{
head=head->next;
}
else //如果被删除的节点，不位于链表头
{
p=q->next;
q->next=p->next;
}
return head; //返回头指针
}
};输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {} //结构体的构造函数，C++中有，C中没有
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) { //温馨提示：要注意head 在不同的递归函数里充当的角色
if( head==NULL||head->next==NULL )
return head;
int i;
ListNode *re_head=head;
re_head=reverseList( re_head->next ); //递归在这里，递归的调用点。结合那个思路图来看，清晰一点
head->next->next=head; //再次提示：要注意head 在不同函数里充当的角色
head->next=NULL;
return re_head;
}
};输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
应用背景（自己琢磨想的）：把两个学校的考生成绩糅合到一起，并且升序排列。
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode prehead(-1); //哑结点，初始值赋为-1，调用的结构体里的构造函数
ListNode *pre=&prehead;
if( l1==NULL ) //如果有一个链表为空，直接返回另一个链表
return l2;
if( l2==NULL )
return l1;
while( l1!=NULL&&l2!=NULL ) //如果 指针l1和l2 中有一指向“空”（即指向NULL）了后，直接跳出
{
if( l1->val val )
{
pre->next=l1;
l1=l1->next;
}
else
{
pre->next=l2;
l2=l2->next;
}
pre=pre->next;
}
if( l1==NULL ) //处理最后剩下一根“红线”（我的思路图里的 最后那根 红线 ）
pre->next=l2;
else
pre->next=l1;
return prehead.next;
}
};输入: 1->2
输出: false
输入: 1->2->2->1
输出: true
应用背景（自己琢磨想的）：来了来了，“回文链表”是“反转链表”的亲戚。实际应用的东西，
我还没想出来。但和“回文数”、“回文字符串”都有相似之处。
思路:我用了一个vector容器，来装这个链表的每个节点的信息。因为链表的特殊性（ 单个指针不能倒着依次访问链表 ）。但数组可以，
而我这里就用了vector的一些数组的功能。 当然，我在论坛中看到有些大佬用递归的方法，琢磨很久，还是没看懂。C++悟力尚浅~~~
实现：（C++）
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector
int i;
ListNode *p=head;
while( head )
{
v1.push_back( head->val ); //①新学到一个函数push_back( 变量 )， 每次向容器末尾插入一个元素
head=head->next;
}
for( i=0;i
if( v1[i]!=v1[ v1.size()-1-i ] ) //来来回回比较
return false;
}
return true;
}
};-----------------------------------------------------------------------------------------------------------
第6题：环形链表
题目描述：pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
应用背景（自己琢磨想的）：感觉用处很广。判断网络信息流通是否有“滞留点”。
感觉以后会有用，现在还没想到深的东西。
思路：使用双指针（一个走得快一点：快指针。一个走得慢一点：慢指针）。一个快一个慢。如果有“环”，那就像在操场的
跑道上，快指针肯定会慢慢地追上慢指针。进而进行区分是否有“环”。
实现:（C++）
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast=head; //快指针
ListNode *slow=head; //慢指针
while( fast!=NULL&&fast->next!=NULL ) //如果快指针能走到“空”（也就是，最终它能指向NULL），说明该链表无“环”
{
fast=fast->next->next; //快指针每次“走”两步
slow=slow->next; //慢指针每次“走”一步
if( fast==slow ) //两个指针相遇了，说明有环
return true;
}
return false;
}
};
