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

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-linked-list-elements

法一描述：

法一代码


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct  ListNode* cur = head, * prve = NULL;
 
    while (cur)
    {
        if (cur->val == val)
        {
            //两种情况头删、非头删
 
            //1头删
            if (cur == head)
            {
                head = head->next;
                free(cur);
                cur = head;
            }
            else//2非头删
            {
                prve->next = cur->next;
                free(cur);
                cur = prve->next;
 
            }
        }
        else
        {
            prve = cur;
            cur = cur->next;
        }
 
    }
    return head;
}

法二描述：

法二代码


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*cur = head;
    struct ListNode*newhead = NULL, *tail = NULL;
 
    while(cur)
    {
        if(cur->val != val)
        {
            if(tail == NULL)
            {
                newhead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
 
            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    //最后节点需要置空，并且当链表为空的时候需要判断一下
    if(tail)
        tail->next = NULL;
 
    return newhead;
}

优化

引入哨兵头的概念

优化


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    //不需要newhead了
    //struct ListNode* newhead = NULL, *tail = NULL;
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = head;
    struct ListNode* tail = guard;
 
    while(cur)
    {
        if(cur->val != val)
        {
            //引入头的概念就不需要下面的判断了
            // if(tail == NULL)
            // {
            //     newhead = tail = cur;
            // }
            // else
            // {
            //     tail->next = cur;
            //     tail = tail->next;
            // }
 
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    //最后节点需要置空，并且当链表为空的时候需要判断一下
    if(tail)
        tail->next = NULL;
 
    //注意释放内存
    head = guard->next;
    free(guard);
 
    return head;
}

21. 合并两个有序链表

描述

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

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

输入：l1 = [], l2 = []
输出：[]
示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists

利用哨兵位可以很好的解决这个问题

代码


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
        //防止有链表为空,所以guard首先置为空
        guard->next = NULL;
 
        struct ListNode* tail = guard;
        struct ListNode* cur1 = list1,*cur2 = list2;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }
 
    if(cur1)
        tail->next = cur1;
    if(cur2)
        tail->next = cur2; 
 
    struct ListNode* head = guard->next;
    free(guard);
 
    return head;
 
}

206. 反转链表

描述

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

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

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

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list

思路一：

画图一步一步分析，会很容易理解

代码


struct ListNode* reverseList(struct ListNode* head){
 
        struct ListNode* cur = head;
        struct ListNode* newhead = NULL;
 
        while(cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
 
            cur = next;
        }
 
    return newhead;
}

思路二：

代码


struct ListNode* reverseList(struct ListNode* head){
 
        struct ListNode* n1,*n2,*n3;
 
        n1 = NULL;
        n2 = head;
        n3 = NULL;
 
        while(n2)
        {
            n3 = n2->next;
 
            n2->next = n1;
 
            n1 = n2;
            n2 = n3;
        }
    return  n1;
}

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，

这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/middle-of-the-linked-list

简单的题目 -- 遍历一般链表记录个数，然后个数除以2得到中间的节点

进阶版

-- 只允许遍历一般链表

思路 -- 快慢指针

定义两个指针，fast(快) slow(慢) ，快指针一次走两步、慢指针一次走一步

当为奇数个节点时，fast走到尾，slow就走到中间节点了

当为偶数个节点时，fast走到NULL，slow就走到中间节点了


struct ListNode* middleNode(struct ListNode* head){
        struct ListNode* fast , *slow;
 
        slow = fast = head;
 
 
        //当fast为空或者fast->next为空的时候结束
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
 
    return slow;
}

链表中倒数第k个结点

这是牛客网上面的一道题目

描述

输入一个链表，输出该链表中倒数第k个结点。

示例1

输入：
1,{1,2,3,4,5}
复制返回值：
{5}
链表中倒数第k个结点_牛客网 -- 链接

代码


struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* fast , *slow;
    fast = slow = pListHead;
    
    //走K-1步，再同时走
    //while(--k);    //不过这样写要注意
    //走K步，再同时走
 
    while(k--)
    {
        if(fast == NULL)    //判断空链表 -- fast指向空就停下来
        {
            return NULL;
        }
        fast = fast -> next;
    }
    
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;  
    }
    return slow;
}

CM11 链表分割

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

链表分割_牛客网 (nowcoder.com)

在牛客网上只支持C++ ，不过用C也可以写

代码


/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessGuard,*lessTail,*greaterGuard,*greaterTail;
        lessGuard = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterGuard = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessGuard->next =  NULL;  //首先置空防止空链表的出现
        greaterGuard->next =  NULL;
        
        struct ListNode* cur = pHead;
        while(cur)    //当cur指向空的时候停下来
        {
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;        
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;            
            }
            
            cur = cur->next;    //cur向后移动
        }   
        lessTail->next = greaterGuard->next;    //把两条链表链接起来
        greaterTail->next = NULL;     //最后 greaterTail->next 要置空防止出现极端情况3
        
        pHead = lessGuard->next;    //重新赋值给原来的头
        free(greaterGuard);        //释放内存
        free(lessGuard);
        
        return pHead;
    }
};

234. 回文链表

描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

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

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

来源：力扣（LeetCode）
链接：234. 回文链表

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

代码


class Solution {
public:
    //找到中间的节点
    struct ListNode* middleNode(struct ListNode* head){
        struct ListNode* fast , *slow;
 
        slow = fast = head;
 
 
        //当fast为空或者fast->next为空的时候结束
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
 
    return slow;
}
 
    //反转链表
struct ListNode* reverseList(struct ListNode* head){
 
        struct ListNode* n1,*n2,*n3;
 
        n1 = NULL;
        n2 = head;
        n3 = NULL;
 
        while(n2)
        {
            n3 = n2->next;
 
            n2->next = n1;
 
            n1 = n2;
            n2 = n3;
        }
    return  n1;
}
 
    bool isPalindrome(ListNode* head) {
        //调用找到中间的节点函数
            struct ListNode* mid = middleNode(head);
        //调用反转链表函数
            struct ListNode* rmid = reverseList(mid);
 
        struct ListNode* cur = head;
 
        while(rmid)
        {
            if(cur->val == rmid->val)
            {
                rmid = rmid->next;
                 cur = cur->next;
            }
            else
            return false;        
        }
 
        return true;
 
 
    }
};

第二种思路：先copy一个链表，然后再逆置copy出来的全部的链表，再和原来比较。不复制原来的链表是不行的，因为这相当于修改了链表了

160. 相交链表

描述

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

160. 相交链表 -- 描述过长进去看

时间复杂度O(N^2)思路 -- 直接暴力求解

优化

代码


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //判断是否为空链表
    if(headB  == NULL || headA == NULL)  //测试结果leetcode并没有给定空链表的测试用例
        return NULL;
    //一般的情况下不改变原来的链表头  因为后面容易用到
    struct ListNode* curA = headA , *curB = headB;
 
    //找尾节点，并记录节点个数
    int lenA = 1; 
    while(curA->next) //因为是找尾所以先设置长度为1
    {
        curA = curA->next;
        ++lenA;
    }
 
    int lenB = 1;
    while(curB->next)
    {
        curB = curB->next;
        ++lenB;
    }
 
    //比较尾节点，如果是相交的话尾节点一定相同
    if(curA != curB)
    {
        return NULL;    //两个链表不相交，因此返回 null 
    }
 
    //下面是建立在相交的情况下找交点的
    //比较那个更长，可以先定curA较长
    struct ListNode* longlist = headA , *shortlist = headB;
    if(lenA < lenB)
    {
        longlist = headB;
        shortlist = headA; 
    }
 
    int gap = abs(lenA - lenB); //abs是用来求绝对值的
    //让长的先走差距步
      while(gap--)
      {
          longlist = longlist->next;
      }  
    //再一起走
        while(longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
 
        return longlist;
}

141. 环形链表

描述

给你一个链表的头节点 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 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

来源：力扣（LeetCode）
链接：141. 环形链表

代码


bool hasCycle(struct ListNode *head) {
    //快慢指针
    struct ListNode* fast , *slow;
    fast = slow = head;
    while(fast && fast->next)    //防止空指针的访问，为空链表就不进去了
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            return true;
    }
 
    return false;
    
}

延申问题

142. 环形链表 II

中等

给定一个链表的头节点 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 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

142. 环形链表 II - 力扣（LeetCode）

法一

代码


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
            struct ListNode* slow = head , *fast = head;
 
            while(fast && fast->next )    //先判断空链表的问题
            {
                slow = slow->next;
                fast = fast->next->next;
                if(fast == slow)    //当相遇时停下循环，进入这一层
                {
                struct ListNode* ListA = head, *ListB = slow;
                while(ListA != ListB)    //一起走，直到找到入口点
                    {
                        ListA = ListA->next;
                        ListB = ListB->next;
                    }
                 return ListA;
                }
            }
 
        return NULL;
    
}

法二

代码

这个方法容易理解


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
//这里是把 141.环形链表 稍作修改
struct ListNode *  hasCycle(struct ListNode *head) {
    //快慢指针
    struct ListNode* fast , *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            return fast;
    }
 
    return NULL; 
 
}
 
//这里是 160.相交链表 稍作修改
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
 
    //一般的情况下不改变原来的链表
    struct ListNode* curA = headA , *curB = headB;
 
    //找尾节点，并记录节点个数
    int lenA = 1; 
    while(curA->next) //因为是找尾所以先设置长度为1
    {
        curA = curA->next;
        ++lenA;
    }
 
    int lenB = 1;
    while(curB->next)
    {
        curB = curB->next;
        ++lenB;
    }
 
    //比较那个更长，可以先定curA较长
    struct ListNode* longlist = headA , *shortlist = headB;
    if(lenA < lenB)
    {
        longlist = headB;
        shortlist = headA; 
    }
 
    int gap = abs(lenA - lenB); //abs是用来求绝对值的
    //让长的先走差距步
      while(gap--)
      {
          longlist = longlist->next;
      }  
    //再一起走
        while(longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
 
        return longlist;
}
 
struct ListNode *detectCycle(struct ListNode *head) {
    //找到相遇节点
    struct ListNode * meet = hasCycle(head);
    //如果为空就直接返回NULL
    if(meet == NULL)
    return NULL;
 
    //新链表B
    struct ListNode * ListB = meet->next;
    //把原来的置空 -- 防止找到B
    meet->next = NULL;
    //新链表A
    struct ListNode * ListA = head;
 
    //返回并保存目标节点
   struct ListNode *entryNode =  getIntersectionNode(ListA,ListB);
   meet->next = ListB;//恢复成原链表 -- 为了不破坏原链表
   return entryNode;
 
}

138. 复制带随机指针的链表

中等

138. 复制带随机指针的链表 - 力扣（LeetCode） -- 进去看看呗

法一

提供思路：1、遍历原链表，复制节点 -- 一个一个尾插

2、更新random，找random原链表中第i个

对应新链表中第i个 -- 即一一对应，因为可能节点中的值一样，

靠值找random是不靠谱的

时间复杂度：O(N^2)

法二

时间复杂度：O(N)

代码


/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
 
struct Node* copyRandomList(struct Node* head) {
	//1.插入copy节点
    //保存头节点指针，防止头被改动，找不到头
    struct Node* cur = head;
    //先创立指针，方便使用
    struct Node* copy = NULL;
    struct Node* next = NULL;
    while(cur)  //当为空的时候停下来
    {
        //链接
        //保存cur的下一个节点，为链接准备
        next = cur->next;
        copy = (struct Node*)malloc(sizeof(struct Node));
        //拷贝数据
        copy->val = cur->val;
 
        cur->next = copy;
        copy->next = next;
 
        //迭代向后走
        cur = next;
    }
 
    //2.更新copy->random
    //重新指向头
    cur = head;
    while(cur)
    {
        //更新copy
        copy = cur->next;
 
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;
 
        //迭代,向后走
        cur = cur->next->next;
    }
 
    //3.把copy节点解下来链接一起，并恢复原链表
    //创立两个方便尾插
    struct Node* copyHead = NULL, * copyTail = NULL;
    //重新指向
    cur = head;
    while(cur)  //cur为空停下来
    {
        //更新copy并保留cur->next->next,尾恢复原链表准备
        copy = cur->next;
        next = copy->next;
 
        //取节点尾插
        //判断为空的时候 -- 尾插
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy; 
        }
        //尾插
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
 
        //恢复原链表
        cur->next = next;
 
        //迭代
        cur = copy->next;
 
    }
    return copyHead;
}

结束语

读书不觉春已深，一寸光阴一寸金。
唐·王贞白《白鹿洞二首·其一》

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/561203