链表刷题集合

链表刷题集合

160. 相交链表

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

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

思路：
1.先找出两条链表中较长的哪一个
2.让长链表先走他们的差距部，让其两者头指向同一位置
3.两个一起开始走，当两者相等时就返回该节点，循环完之后没有返回就返回null
特殊情况处理：
1.当两个链表的头指针都为null时，返回努力了
2.当两者头节点有一个为null时也返回null

注意：
链表中找相交结点时一定找的是他们的地址相同处，因为链表的结点都是动态开辟的，第一个相交结点他们的地址
一定相同，而不能只是简单的比较一下值

代码

/**

 * Definition for singly-linked list.

 * struct ListNode {

 * int val;

 * struct ListNode *next;

 * };
   *///思路：1.找到两个链表中较大的那一个，然后让长链表先走他们的差距部，等到他们位于同一起点，然后两者//       一起走，直到两者到达同一节点处和//特殊情况的处理：//1.两个链表的只想都为null，返回true，两个链表中只有一个指向为null，返回falsestructListNode*getIntersectionNode(structListNode*headA,structListNode*headB){//1.两个头指针都为nullif(headA==NULL&&headB==NULL){return headA;}//2.两个结点其中一个为空if(headA==NULL||headB==NULL){returnNULL;}//3.排除特殊情况之后，我们就要开始处理正常情况int LenA=0,LenB=0;structListNode*curA=headA;structListNode*curB=headB;while(curA!=NULL){
       LenA++;
       curA=curA->next;}while(curB!=NULL){
        LenB++;
        curB=curB->next;}int n=abs(LenA-LenB);if(LenA>LenB){while(n--){
            headA=headA->next;}}else{while(n--){
            headB=headB->next;}}
    curA=headA;
    curB=headB;while(curA!=NULL&&curB!=NULL){if(curA==curB){return curA;}
        curA=curA->next;
        curB=curB->next;}returnNULL;}

203. 移除链表元素

给你一个链表的头节点

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
输出：[]

本题是一道简单题，但是仍然有几个需要注意的点：

1.如果头指针直接为空

2.头指针不为空但只有一个元素且为要删除的元素

3.全部都是要删除的元素

最好的方式就是定义一个哨兵位的头节点，然后向后遍历删除val，这样就避免了头指针为空的情况和头指针不为空且只有一个元素或者要删除的元素是链表的全部结点，这种方式代码如下所示：

*** Definition for singly-linked list.*structListNode{*int val;*structListNode*next;*};*/structListNode*removeElements(structListNode* head,int val){//创建一个哨兵位的头节点structListNode*pHead=(structListNode*)malloc(sizeof(structListNode));//连接头节点和这个链表的元素
    pHead->next=head;//cur指向现在的头节点structListNode*cur=pHead;//prev作为前驱指针structListNode*prev=NULL;while(cur!=NULL){//如果cur->val==val，执行删除操作，其中prev指向前驱指针，Next指向要删除元素的下一个地方if(cur->val==val){structListNode*Next=cur->next;
            prev->next=Next;free(cur);
            cur=Next;}else{
        此时prev总是比cur少一个
            prev=cur;
            cur=cur->next;}}return pHead->next;}

如果不用这种方式，而是要用普通方法创建，就比较复杂，考虑全上面3中情况，代码如下：

/** * Definition for singly-linked list. 
* struct ListNode { 
*     int val;
*     struct ListNode *next; 
* }; 
*/structListNode*removeElements(structListNode* head,int val){//本题特殊情况：当头结点为val时structListNode*cur=head;structListNode*prev=NULL;while(cur!=NULL){structListNode*next=cur->next;if(cur->val==val){//当第一个节点为val时，代表prev为空，那我们直接释放这个节点，然后让head指针指向下一个元素 //然后让将下一个节点赋给curif(prev==NULL){ 
                 head=next;free(cur);
                 cur=next;}//当第一个节点不为空时，我们使prev直接指向cur的下一个元素，释放cur,将next赋给curelse{
                prev->next=next;free(cur); 
                cur=next;}}//如果该节点不是val，那么将cur赋给prev,然后cur指向下一个元素else{
            prev=cur; 
            cur=cur->next;}}return head;

剑指 Offer II 024. 反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

这里我们有两种方法进行书写

方法一：头插法：将每一个节点进行头插，这样实现对链表的逆置

classSolution{public:
    ListNode*reverseList(ListNode* head){//判断头结点是否为空if(head==nullptr)returnnullptr;
        ListNode*cur=head;//创建新的头结点
        ListNode*NewHead=nullptr;while(cur){
            ListNode*next=cur->next;//使当前节点的下一个元素指向新的头结点
            cur->next=NewHead;//使得cur成为新的头节点
            NewHead=cur;
            cur=next;}return NewHead;}};

148. 排序链表

你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

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

示例 2：

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

示例 3：

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

链表排序的最佳方法：归并排序

1.找到中间节点

2.将中间节点断成左右两半，然后再次递归找到中间节点，再次进行分割，直到最后分割成一个一个的单个元素

3.然后两两排序，之后四四排序…直到最后将整张链表排成一个有序链表

这个思想和归并排序一样，归并排序的原理也是将数据分割成小部分，然后每一个小部分进行排序，让局部有序，然后整体有序

classSolution{public://链表的排序：归并排序//1.找到中间节点//2.将链表分为两部分//3.实现有序链表的排序
    ListNode*Sort(ListNode*&l,ListNode*&r){//到这里就是排序的思想了，排序思想和合并两个有序链表的思想差不多//创建新的节点，然后按照插入排序的思想，谁大谁就插入
        ListNode*dummyHead=newListNode(0);
        ListNode*cur=dummyHead;while(l!=nullptr&&r!=nullptr){if(l->val<=r->val){
                cur->next=l;
                cur=cur->next;
                l=l->next;}else{
                cur->next=r;
                cur=cur->next;
                r=r->next;}}if(l!=nullptr){
            cur->next=l;}if(r!=nullptr){
            cur->next=r;}return dummyHead->next;}//传递参数时记得引用传递
    ListNode*MergSort(ListNode*&head){//判断头节点的下一个节点是否为空，如果是，直接返回头节点if(head->next==nullptr)return head;//定义快慢指针，寻找中间节点
        ListNode*slow=head;
        ListNode*fast=head;
        ListNode*prev=nullptr;while(fast&&fast->next){
            prev=slow;
            slow=slow->next;
            fast=fast->next->next;}//此时slow所在的位置就是中间节点所在的位置，prev指向slow的前一个节点//我们人为的让链表从slow这个地方断开，head->prev是链表的前半段，slow到完是链表的右半部分
        prev->next=nullptr;//递归在左、右两端继续找中间节点
        ListNode*l=MergSort(head);
        ListNode*r=MergSort(slow);//当分割的不能分割时，进行排序，最开始两两排序，到后来四四排序returnSort(l,r);}
    ListNode*sortList(ListNode* head){//1.判断节点是否为空if(head==nullptr)return head;//2.进入归并排序，寻找中间节点returnMergSort(head);}};

725. 分隔链表

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

输入：head =[1,2,3], k =5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 为 output[0].val =1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

输入：head =[1,2,3,4,5,6,7,8,9,10], k =3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

思路：

1.求链表得节点个数

2.如果节点个数<K，说明节点个数不够分割，那么就让前面几个节点单独为一个，后面的都为NULL，凑齐k个

3.链表节点>K并且有剩余，那么我们就k个节点为一组，如果有剩余，那么剩余的节点每次多添加一个给前面的节点

classSolution{public:
    vector<ListNode*>splitListToParts(ListNode* head,int k){
        vector<ListNode*>ret;//首先遍历得到链表的长度//每k个一组进行分割，分别进入链表
        ListNode*cur=head;int sum=0;while(cur){
            sum++;
            cur=cur->next;}int temp=sum/k;//判断每组有多少个节点
        cur=head;//temp==0说明链表节点少于K个，那么就将链表单独分割，不足的用nullptr代替if(temp==0){//此时说明k>sum,说明不够分while(k--){if(cur){
                    ListNode*next=cur->next;
                    cur->next=nullptr;
                    ret.push_back(cur);
                    cur=next;}else{
                    ret.push_back(nullptr);}}return ret;}//让cur重新指向头
        cur=head;//next用来记录cur得下一个位置
        ListNode*next=cur->next;//phead指向cur的起始位置，以便于后续将该节点加入到数组中
        ListNode*phead=cur;//判断有没有余数，如果有余数则一次让前面几个组的temp值+1int remind=sum%k;//k用来控制外层循环，即用来表示要分的组数while(k--){//里面即表示每组的成员int val=temp;if(remind!=0)
            val+=1;//从cur位置开始往后走val步即到达每个组的数量while(--val){
                cur=cur->next;}
            next=cur->next;if(cur!=nullptr)
            cur->next=nullptr;//入数组
            ret.push_back(phead);//重新使cur指向下一个位置
            cur=next;//phead重新指向cur的起始位置
            phead=cur;//余数--if(remind)
            remind--;}return ret;}};

430. 扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：

扁平化后的链表如下图：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

1—2—NULL
|
3—NULL
示例 3：

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

思路：将该图旋转一下，发现它非常像一颗二叉树，child相当于左孩子，next相当于右孩子，那么我们只要前序遍历这颗二叉树，就能得到正确答案

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/classSolution{public://创建全局变量，设置一个哨兵位置的头节点
      Node*dummy=newNode();
        Node*p=dummy;voiddfs(Node*&head){//将head连接到p->next
        p->next=newNode();
        p->next->val=head->val;
        p->next->prev=p;
        p=p->next;//递归遍历左子树if(head->child){dfs(head->child);}//递归遍历右子树if(head->next){dfs(head->next);}}
    Node*flatten(Node* head){//判断头节点是否为空if(head==nullptr)returnnullptr;dfs(head);//将最后一个节点的下一个位置置为nullptr
        p->next=nullptr;//将第一个节点与前面哨兵位置断开
       dummy->next->prev=nullptr;return dummy->next;}};

删除有序链表中重复的元素-I

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1->1->-2,返回1->2.
给出的链表为1->1->2->3->3,返回1→2→3.

数据范围：链表长度满足 0 \le n \le 1000≤n≤100，链表中任意节点的值满足 |val| \le 100∣val∣≤100
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

输入：
{1,1,2}
复制
返回值：
{1,2}

​ 代码如下所示

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */classSolution{public:/**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode*deleteDuplicates(ListNode* head){// write code hereif(head==nullptr||head->next==nullptr){return head;}
        ListNode*cur=head;while(cur&&cur->next){
            ListNode*next=cur->next;//前后双指针进行判断if(cur->val==next->val){
                cur->next=next->next;delete next;}else{
                cur=cur->next;}}return head;}};

删除有序链表中重复的元素-II

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度 0 \le n \le 100000≤*n*≤10000，链表中的值满足 |val| \le 1000∣*v**a**l*∣≤1000

要求：空间复杂度 O(n)*O*(*n*)，时间复杂度 O(n)*O*(*n*)

进阶：空间复杂度 O(1)*O*(1)，时间复杂度 O(n)*O*(*n*)

示例1
输入：
{1,2,2}
复制
返回值：
{1}

代码示例

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */classSolution{public:/**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode*deleteDuplicates(ListNode* head){// write code here//哈希映射，判断是否有重复值//文中题目结点的val范围为|val|<=1000//也就是-1000<=val<=1000//我们人为映射统计每个节点出现的次数，然后判断是不是只出现了一次//我们可以创建一个大小为2000的数组，为什么是2000呢，因为数组范围-1000，1000//我们无法直接映射负数到数组中，每次让val+1000即可//即-1000+1000<=val+1000<=1000+1000;//一次遍历映射，判断是否出现一次，这样也符合题目要求的时间复杂度为O(N)，空间负责都为O(1)// write code here//哈希映射，判断是否有重复值int*arr=newint[2000]; 
        ListNode*cur=head;while(cur){
            arr[cur->val+1000]++;
            cur=cur->next;}
        cur=head;//建立头结点
        ListNode*NewHead=newListNode(0);
        ListNode*tail=NewHead;while(cur){if(arr[cur->val+1000]==1){
                tail->next=cur;
                tail=tail->next;}
            cur=cur->next;}
        tail->next=nullptr;return NewHead->next;}};

  //我们无法直接映射负数到数组中，每次让val+1000即可
    //即-1000+1000<=val+1000<=1000+1000;
    //一次遍历映射，判断是否出现一次，这样也符合题目要求的时间复杂度为O(N)，空间负责都为O(1)
    // write code here
    //哈希映射，判断是否有重复值
    int*arr=new int[2000]; 
    ListNode*cur=head;
    while(cur)
    {
        arr[cur->val+1000]++;
        cur=cur->next;
    }
    cur=head;
    
    //建立头结点
    ListNode*NewHead=new ListNode(0);
    ListNode*tail=NewHead;
    while(cur)
    {
        if(arr[cur->val+1000]==1)
        {
            tail->next=cur;
            tail=tail->next;
        }
        cur=cur->next;
    }
    tail->next=nullptr;
    return NewHead->next;
}

};