链表算法速成计划
1.准备工作
1.1创建链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
1.2 在IDE中创建链表代码
ListNode* createRandomLinkedList(int length)
{
if (length <= 0) return NULL;
// 设置随机数种子
std::random_device rd; // 随机数种子
std::mt19937 gen(rd()); // Mersenne Twister 随机数引擎
std::uniform_int_distribution<> dis(0, 99); // 随机数分布
// 创建头节点，数据为0到99之间的随机值
ListNode* head = NULL;
// 循环创建其他节点
for (int i = 1; i < length; ++i)
{
ListNode* newListNode = new ListNode(dis(gen) % 100);
newListNode->next = head;
head = newListNode;
}
return head;
}
1.3 打印链表和释放链表代码
// 打印链表的函数
void printLinkedList(ListNode* head)
{
ListNode* current = head;
while (current != NULL)
{
std::cout << current->val << " -> ";
current = current->next;
}
std::cout << "NULL" << std::endl;
}
// 释放链表内存的函数
void freeLinkedList(ListNode* head)
{
ListNode* current = head;
while (current != NULL)
{
ListNode* nextListNode = current->next;
delete current;
current = nextListNode;
}
}
1.4 示例代码
#include <iostream>
#include <random>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* createRandomLinkedList(int length)
{
if (length <= 0) return NULL;
// 设置随机数种子
std::random_device rd; // 随机数种子
std::mt19937 gen(rd()); // Mersenne Twister 随机数引擎
std::uniform_int_distribution<> dis(0, 99); // 随机数分布
// 创建头节点，数据为0到99之间的随机值
ListNode* head = NULL;
// 循环创建其他节点
for (int i = 1; i < length; ++i)
{
ListNode* newListNode = new ListNode(dis(gen) % 100);
newListNode->next = head;
head = newListNode;
}
return head;
}
// 打印链表的函数
void printLinkedList(ListNode* head)
{
ListNode* current = head;
while (current != NULL)
{
std::cout << current->val << " -> ";
current = current->next;
}
std::cout << "NULL" << std::endl;
}
// 释放链表内存的函数
void freeLinkedList(ListNode* head)
{
ListNode* current = head;
while (current != NULL)
{
ListNode* nextListNode = current->next;
delete current;
current = nextListNode;
}
}
int main() {
// 创建链表
for (int i = 1; i <= 5; i++)
{
ListNode* head = createRandomLinkedList(10);
cout << "第" << i << "次样例:";
printLinkedList(head);
//本区域填写你的函数！！！！
//ListNode* newhead = 你的函数(head);
cout << "第" << i << "次结果:";
printLinkedList(head);
// 释放链表内存
freeLinkedList(head);
}
return 0;
}
2. 基本操作（必须熟练默写！）
2.1 头插
ListNode* head_insert(ListNode* head, ListNode* node) //head为链表，ListNode为待插入节点
{
//本代码正常head为NULL，也就是空链表
node->next = head; //ListNode指向head
head = node; //让ListNode作为新的头
return head;
}
示例
int main() {
ListNode* head = NULL;
for (int i = 1; i <= 5; i++)
{
ListNode* newhead = new Node(i);
head = head_insert(head, newhead);
cout << "第" << i << "次插入结果:";
printLinkedList(head);
}
return 0;
}
2.2 头删
ListNode* head_delete(ListNode* head) //head为链表
{
if (head == NULL)return head; //为空就直接返回
ListNode* cur = head; //记录待删除节点
head = head->next; //头结点只想下一个
free(cur); //释放cur结点
return head;
}
示例
int main() {
ListNode* head = NULL;
for (int i = 1; i <= 5; i++)
{
Node* newhead = new Node(i);
head = head_insert(head, newhead);
cout << "第" << i << "次插入结果:";
printLinkedList(head);
}
for (int i = 1; i <= 5; i++)
{
head = head_delete(head);
cout << "第" << i << "次删除结果:";
printLinkedList(head);
}
return 0;
}
2.3 中间节点插入（包括尾插）
ListNode* middle_insert(ListNode* head, int val, ListNode* node) //本代码理解意思即可，也就是说先查找到val值的节点，然后在其后面插入ListNode，尾插也可以用这个思想！
{
ListNode* pre = head; //pre指插入位置的前一个节点也就是val值的节点
while (pre)
{
if (pre->val != val) //如果没有找到val就继续找
pre = pre->next;
else //找到val后进行插入
{
node->next = pre->next;
pre->next = node;
break; //插入后退出循环
}
}
return head; //返回链表头节点
}
示例
int main() {
ListNode* head = NULL;
for (int i = 1; i <= 5; i++)
{
ListNode* newhead = new ListNode(i);
head = head_insert(head, newhead);
cout << "第" << i << "次插入结果:";
printLinkedList(head);
}
//在1后面插入10
ListNode* newhead = new Node(10);
middle_insert(head, 1, newhead);
cout << "插入结果:";
printLinkedList(head);
//在5后面插入20
newhead = new Node(20);
middle_insert(head, 5, newhead);
cout << "插入结果:";
printLinkedList(head);
return 0;
}
2.4 删除中间节点（包括尾删）
ListNode* middle_delete(ListNode* head, int val) //先查找到val对应的节点，然后删除该节点
{
ListNode* pre = NULL; //pre是需要删除节点的前一个位置，注意：在删除节点中前一个位置很重要，因为你只有通过前一个结点才能将链表连接起来！
if (head->val != val) //如果需要删除的是第一个节点，那么他没有前一个节点，所以你得判断一下，如果删除的不是第一个节点，那么就可以将head赋值给pre，然后进行查找
{
pre = head;
}
else //如果要删除的是第一个节点也就是头删！
{
head = head_delete(head);
return head;
}
while (pre->next) //pre->next就是我们要查找的待删除节点，所以这个一定不是NULL的，故while条件是这个
{
if (pre->next->val != val) //如果不等就往下一个查找
{
pre = pre->next;
}
else //如果查到
{
ListNode* cur = pre->next; //记录待删除节点
pre->next = cur->next; //连接前后节点
free(cur);
break;
}
}
return head;
}
示例
int main() {
ListNode* head = NULL;
for (int i = 1; i <= 5; i++)
{
ListNode* newhead = new ListNode(i);
head = head_insert(head, newhead);
cout << "第" << i << "次插入结果:";
printLinkedList(head);
}
head = middle_delete(head,4);
cout << "删除4后结果:";
printLinkedList(head);
head = middle_delete(head, 5);
cout << "删除5后（也就是删除第一个位置）结果:";
printLinkedList(head);
head = middle_delete(head, 1);
cout << "删除1后（也就是删除最后个位置）结果:";
printLinkedList(head);
return 0;
}
3. 力扣代码练习
3.1 合并两个有序链表
/**
* 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* list1, ListNode* list2) {
ListNode* newhead=new ListNode(-1);//创建哨兵头节点
ListNode* tail=newhead;//永远指向新链表的尾部的节点
while(list1&&list2)
{
if(list1->val<list2->val)//如果list1头节点小就让list1头节点尾插到newhead
{
ListNode* cur=list1;//cur是指向该头节点
list1=list1->next;//然后list1就指向他的下一个节点，也就是丢弃了之前的头节点
tail->next=cur;//newhead尾节点指向cur节点
tail=tail->next;//tail更新到下一个节点
}else
{//同上
ListNode* cur=list2;
list2=list2->next;
tail->next=cur;
tail=tail->next;
}
}
if(list1!=nullptr)//到这一步就是会出现要么list1还剩余节点，list2没有，要么list2还剩余节点，list1没有，这个时候只需要将整条链接到newhead尾巴后面
{
tail->next=list1;
}
if(list2!=nullptr)
{
tail->next=list2;
}
return newhead->next;//返回头节点（要范围next，应为newhead是哨兵）
}
};
3.2 删除排序链表中的重复元素
/**
* 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* deleteDuplicates(ListNode* head) {
ListNode* pre=head;//pre指向要删除节点的前一个位置，也就是说pre是指第一个出现该数字的节点，之前后的相同节点都要被删除
while(pre&&pre->next)//这里也要保证pre->next不是空，因为可能pre是最后一个节点，那么就没有意义了，也就是说这个循环条件是运行到倒数第二个节点
{
if(pre->val==pre->next->val)//如果相等这删除这个节点，然后继续循环
{
//ListNode* cur=pre->next;
pre->next=pre->next->next;
//free(cur);//考试的时候需要这样写，也就是要释放结点，但是OJ不给你释放所以我就屏蔽掉这两行代码！
}
else//如果不相等就pre指向下一个节点， 如果不懂自己根据样例画图看看
{
pre=pre->next;
}
}
return head;
}
};
3.3 环形链表
/**
* 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&&fast->next)//这里的判断条件是防止fast走到NULL，出现空指针异常 因为fast每次要走两步，所以要保证fast可以走到第二步，也就是说fast和fast->next都不能为空
{
fast=fast->next->next;//fast走两步
slow=slow->next;//slow走一步
if(fast==slow)return true;//如果是循环链表，那么fast一定会追上slow，然后就返回true
}
return false;//走到这一步是因为head不是循环链表，fast走到尾巴了，故跳出循环
}
};
3.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* removeElements(ListNode* head, int val) {
ListNode* newhead=new ListNode(-1);//创建一个哨兵，处理特殊情况（删除第一个也就是头删要特殊处理比较麻烦）
newhead->next=head;
ListNode* pre=newhead;//需要删除节点的前一个
while(pre&&pre->next)//pre->next是可能需要删除的结点，故他一定要存在
{
if(pre->next->val==val)//如果pre->next和val相同则要删除该节点
{
pre->next=pre->next->next;
}
else//否则pre往下遍历
{
pre=pre->next;
}
}
return newhead->next;
}
};
3.5 反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//头插的应用
ListNode* newhead=NULL;
while(head)
{
ListNode* cur=head;//记录需要头插的结点
head=head->next;//head往下遍历
cur->next=newhead;//cur指向头插链表的头
newhead=cur;//cur作为 新 头插链表的头节点
}
return newhead;
}
};
3.6 链表的中间结点
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast&&fast->next)//查找链表中间节点，快指针走到结束，慢指针正好到中间
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
};
3.7 回文链表
class Solution {
public:
bool isPalindrome(ListNode* head) {//算法思路：找到中间节点，将后面一半反转，然后对比
ListNode* fast=head;
ListNode* slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
//这个时候slow应该是中间节点
//但是这个时候有两个情况
//1. A->B->C 链表长度为奇数时 fast不为空，slow是中间那个节点
//2. A->B->C->D 链表偶数时,fast为空，slow是中间元素上取整，也就是C
//所以这里要分情况
if(fast)
{
slow=slow->next;//这里对应第一种情况，让slow到下一个节点，这样就可以让两种情况的判断过程一样
}
//反转链表:模板，本质就是头插 理解背上
ListNode* newhead=NULL;
while(slow)
{
ListNode* cur=slow;
slow=slow->next;
cur->next=newhead;//头插
newhead=next;
}
while(newhead)//这样就得到两个链表，head和newhead，但是这里newhead肯定是后面半部分，所以我们使用newhead为空来判断是否结束，每次都判断对应节点是否相等，不相等就不是回文串，相等就都往下一个遍历，直到遍历结束那就是回文串
{
if(newhead->val!=head->val)
{
return false;
}
newhead=newhead->next;
head=head->next;
}
return true;
}
};
3.8 删除链表的倒数第 N 个结点
ListNode* removeNthFromEnd(ListNode* head, int n) {
//算法思想：让cur先走n个节点，然后让pre从头开始和cur一起走，cur走到结束了，那么pre就走到要删除节点的前一个（题目翻译就是说让pre少走n个节点）
// 分析样例：1->2->3->4->5->NULL n=2，也就是说我们要删除4，那么我们要找到3这个位置（也就是5-2=3这个位置，那么我们只需要走两次就可以走到3），我们让cur先走2次，然后让pre和cur一起走，一直让cur走到最后一个节点的时候，pre就是要删除节点的前一个位置
ListNode* cur=head;
for(int i=0;i<n;i++)
{
if(cur==NULL)//这个是用来判断n是否合理的，比如说我长度一个是4个，你n给我5那我在遍历head的时候就会出现cur走到结束了，这个时候就什么不要操作直接返回head
return head;
cur=cur->next;
}
if(cur==NULL) return head->next;//这里如果cur走到了尾巴，那么就相当于头插，我们只需要返回头的下一个节点，还是以：1->2->3->4->5->NULL n=5为例，这个时候cur从头5个节点那么就会跑到尾巴，那么这个时候相当于头删
//删除算法中头删和中间删除（尾删）要分别处理，我给你的代码模板中也说了
ListNode* pre=head;
while(cur->next)//cur走到后一个节点
{
cur=cur->next;
pre=pre->next;
}
pre->next=pre->next->next;//删除中间的结点方法
return head;
}
};
3.9 排序链表（本题OJ需要nlogn，但是我们考试写出n^2复杂度就够用，所以使用插入排序思想）
/**
* 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* sortList(ListNode* head) {
//对链表进行排序，使用插入排序思想
ListNode* newhead=NULL;//排序后的头结点
while(head)
{
ListNode* cur=head;//将要插入到新链表的结点
head=head->next;//原来链表头结点到下一个
if(newhead==NULL||cur->val<newhead->val)//如果一开始为空，或者cur比第一个新链表头结点小，那么只能头插
{
cur->next=newhead;
newhead=cur;
}
else
{
ListNode *pre=newhead;//指向将要插入位置的前一个节点
while(pre)
{
if(pre->next==NULL||cur->val<pre->next->val)//pre->next==null是查找到尾巴了，只能插入到最后一个位置，cur->val<pre->next->val是cur比pre->next节点值小，所以就要插入到pre结点后面
// 比如插入1 插入到-1->0->1->2->3 那么根据插入排序思想就是要插入到第一个比自己大的结点前面
{
cur->next=pre->next;
pre->next=cur;
break;//插入成功就跳出循环
}
pre=pre->next;//否则pre就一直往后查找
}
}
}
return newhead;//返回新链表头结点
}
};
