链表知识汇总

给你一个链表的头节点 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
输出：[]

解题代码：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//头结点有时候也要删除，那么就在头结点的前面加个虚拟头结点方便删除头结点ListNode* dumhead = new ListNode(0);dumhead->next = head;ListNode* cur = dumhead;//这个是移动指针while(cur->next!=NULL){if(cur->next->val==val){ListNode* tmp=cur->next;//保存需要删除节点的地址，方便后面进行删除cur->next=cur->next->next;delete tmp;}else{cur=cur->next;}}head=dumhead->next;//返回修改后的链表头地址delete dumhead;return head;}
};

完整ACM模式代码，含链表创建，链表输出打印内容：

#include<iostream>
#include <limits>
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* creatNodeList(){ListNode* head=NULL;ListNode* tail=NULL;  int num;while(cin>>num){ListNode* newnode = new ListNode(num);if(head==NULL){head=newnode;tail=newnode;}else{tail->next=newnode;tail=newnode;}}// 清除 cin 的错误状态以便后续继续输入cin.clear();cin.ignore(numeric_limits<streamsize>::max(), '\n'); tail->next = NULL;return head;
}void printNodeList(ListNode* head){ListNode* current = head;while(current!=NULL){if(current->next!=NULL){cout<<current->val<<" -> ";}else{cout<<current->val<<endl;}current=current->next;}cout<<endl;
}ListNode* removeElements(ListNode* head, int val){//头结点有时候也要删除，那么就在头结点的前面加个虚拟头结点方便删除头结点ListNode* dumhead = new ListNode(0);dumhead->next = head;ListNode* cur = dumhead;//这个是移动指针while(cur->next!=NULL){if(cur->next->val==val){ListNode* tmp=cur->next;//保存需要删除节点的地址，方便后面进行删除cur->next=cur->next->next;delete tmp;}else{cur=cur->next;}}//返回修改后的链表头地址,如果没有这个操作，直接返回head，返回的可能是一个被删除的节点head=dumhead->next;delete dumhead;return head;
}int main(){cout<<"请按照头尾节点顺序依次输入节点值:"<<endl;ListNode* myNode=creatNodeList();cout<<"你输入的链表如下所示:"<<endl;printNodeList(myNode);int val; cout<<"请输入一个需要删除的节点"<<endl;while(cin>>val){myNode=removeElements(myNode,val);cout<<"修改后的链表如下所示:"<<endl;printNodeList(myNode);}return 0;
}

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

/*** 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 dummyHead(0); dummyHead.next=nullptr;//创建一个指针指向虚拟头结点，方便后面合并链表ListNode* p = &dummyHead;//创建两个指针分别指向list1和list2ListNode* p1=list1; ListNode* p2=list2;while(p1!=nullptr&&p2!=nullptr){//比较list1(p1)和list2(p2)哪个值小if(p1->val > p2->val){p->next=p2;//list2(p2)小，就将p2现在这个节点加入到dummyHead(p)链表中p2=p2->next;//list2(p2)对应节点加入后，前进一位}else{p->next=p1;//list1(p1)小，就将p1现在这个节点加入到dummyHead(p)链表中p1=p1->next;//list1(p1)对应节点加入后，前进一位}p=p->next;//dummyHead(p)前移一位}//如果list1(p1)没有了，就把剩下的list2(p2)接在dummyHead(p)后面if(p1==nullptr){p->next=p2;}//如果list2(p2)没有了，就把剩下的list1(p1)接在dummyHead(p)后面if(p2==nullptr){p->next=p1;}//返回dummyHead(p)的next指针，就是新合并链表的第一个节点地址return dummyHead.next;}
};

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,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* partition(ListNode* head, int x) {ListNode dummyNode1(0);//比ListNode dummyNode = ListNode(0);效率高ListNode dummyNode2(0);ListNode* p1 = &dummyNode1;ListNode* p2 = &dummyNode2;ListNode* p = head;while(p!=nullptr){if(p->val<x){p1->next = p;p1=p1->next;}else{p2->next = p;p2=p2->next;}p=p->next;}//在链表的分割操作中，应该确保 p2 结束的节点的 next 指针指向 nullptr，以避免形成环路p2->next=nullptr;//这一步忘记了，程序出现bug了p1->next=dummyNode2.next;return dummyNode1.next;}
};

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {//因为涉及到同时对k个元素大小进行比较，所以本地需要用最小堆自动实现大小排序ListNode dummyNode(0);ListNode* p = &dummyNode;//定义Lambda表达式作为小顶堆比较器auto min = [](ListNode* a , ListNode* b){return a->val > b ->val;//谁大谁的优先级就低};//构建优先级队列（小顶堆）priority_queue<ListNode*,vector<ListNode*>,decltype(min)> minH(min);//将lists里面每个链表的头节点放进去，因为每个链表是升序的for(ListNode* head : lists){if(head!=nullptr){minH.push(head);}}while(!minH.empty()){ListNode* node=minH.top();minH.pop();p->next = node;//头结点比较出最小的后，把这个头结点的后面节点也加入最小堆中if(node->next!=nullptr){minH.push(node->next);}p=p->next;}return dummyNode.next;}
};

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode dummyHead(0);dummyHead.next=head;//这个忘写了，也整错了ListNode* p1 = &dummyHead;ListNode* p2 = &dummyHead;while(n-- && p1!=nullptr){p1=p1->next;}p1=p1->next;//这个得多一步，后面方便删除节点while(p1!=nullptr){//开始写成if了，整错了p1=p1->next;p2=p2->next;}ListNode* temp = p2->next;p2->next=p2->next->next;delete temp;return dummyHead.next;}
};

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow=head;//慢指针每次走一步，用于返回中间节点ListNode* fast=head;//快指针每次走两步，用于遍历整个链表while(fast != nullptr && fast->next != nullptr){//模拟一下来设置边界条件fast=fast->next->next;slow=slow->next;}return slow;}
};

（这道题是我第一次实习面试时候，面试官直接让我写完整实现程序，也就是ACM模式，当时一点也不熟悉，甚至在本地编辑器都不会写ListNode的创建，愣是反应半天没写出来，现在我把完整代码附在下面）

#include<iostream>
#include <limits>
using namespace std;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){}
}; ListNode* creatListNode(){ListNode* head=nullptr;ListNode* tail=nullptr;int num;while(cin>>num){ListNode* newnode = new ListNode(num);if(head==nullptr){head=newnode;//如果头结点是空指针说明还没有节点tail=newnode;//头尾指针都指向第一个节点}else{tail->next=newnode;//尾指针指在最后一个节点，那么这个节点的下个节点插入newnodetail=newnode;//尾指针继续指向最后的节点}}// 清除 cin 的错误状态以便后续继续输入cin.clear();cin.ignore(numeric_limits<streamsize>::max(), '\n'); tail->next = NULL;return head;
}void printNode(ListNode* head){ListNode* p = head;while(p!=nullptr){if(p->next!=nullptr){cout<<p->val<<" -> ";}else{cout<<p->val;}p=p->next;}cout<<endl;
}ListNode* midFindNode(ListNode* inNode){ListNode* fast=inNode;ListNode* slow=inNode;while(fast!=nullptr&&fast->next!=nullptr){fast=fast->next->next;slow=slow->next;}return slow;
}int main(){cout<<"请按照头尾节点顺序依次输入节点值:"<<endl;ListNode* inNode = creatListNode();ListNode* midnode = midFindNode(inNode);cout<<"从中间节点依次往后的节点为："<<endl;printNode(midnode);
}

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

/*和寻找中间节点一样，fast走2步，slow走一步，然后累计差是1,2,3…n，若fast=null，没有环，已到头；若fast=slow，说明相遇，肯定有环。相遇点距离头结点距离就是走的k次，且圆环节点数为k的整数倍(两指针差的距离k)求圆环起点，则让其中一个指针回到都节点，都一次一步，最终相遇点就是圆环起点(图说明更形象)*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow=head;ListNode *fast=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow){break;//说明相遇，赶紧退出，保留指针位置}}if(fast==NULL||fast->next==NULL){return NULL;//有null，没相遇，直接返回null}slow=head;//回退到头指针while(slow!=fast){slow=slow->next;fast=fast->next;}return slow;}
};//快慢指针

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

 /*这道题准备先分别计算各自长度，然后长的先走相差的步数后，慢的再走*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * p1 = headA;ListNode * p2 = headB;int len1=0, len2=0;while(p1!=NULL){len1++;p1=p1->next;}while(p2!=NULL){len2++;p2=p2->next;}ListNode * a1 = headA;ListNode * a2 = headB;if(len1>len2){int len=len1-len2;while(len--){a1=a1->next;}}if(len2>len1){int len=len2-len1;while(len--){a2=a2->next;}}while(a1!=NULL){if(a1==a2){return a1;}a1=a1->next;a2=a2->next;}return NULL;}
};

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* p1=head;ListNode* p2=NULL; //可以将指针设为NULLwhile(p1!=nullptr){ListNode* temp;temp=p1->next;p1->next=p2;p2=p1;p1=temp;}return p2;//写成返回p1了，p1到时候已经是null了}
};