⭐️本篇博客我要给大家分享一下算法中的链表例题。希望对大家有所帮助。
⭐️ 博主码云gitee链接：码云主页

目录

前言

🌏一、移除链表元素（传送门）

🌏二、反转链表（传送门）

🌏三、链表的中间节点 （传送门）

🌏四、链表中倒数第K个节点（传送门）

🌏五、合并两个有序链表（传送门）

🌏六、链表分割（传送门）

🌏七、链表回文（传送门）

🌏八、相交链表（传送门）

🌏九、 环形链表（传送门）

🌏环形指针扩展

🌏十、环形链表||（传送门）

🌏十一、复制带随机指针的列表（传送门）

🌏总结

前言

​

🌏一、移除链表元素（传送门）

🍤给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

 🔑思路：

        三种情况：常规情况，上面图中那种，还有就是连续的val，头就是val。

不管是哪种，就是pre和cur一个一个向后找，直到cur指向null，

当头是val的时候，free cur, 将head和cur移动到next

struct ListNode* removeElements(struct ListNode* head, int val){    struct ListNode* pre = NULL;    struct ListNode* cur = head;    while(cur != NULL){ //如果第一个就是val if(cur->val == val){     struct ListNode* next = cur->next;     //如果pre为空则要删除第一个节点    if(pre != NULL){  free(cur);  pre->next = next;  cur = next;    }else{ free(cur); head = next; cur = next;    } //如果第一个不是val }else{     pre = cur;     cur = cur->next; }    }    return head;}

🌏二、反转链表（传送门）

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

示例 1：

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

 🔑思路1：

        定义三个指针

 首先要判断，head是不是NULL否则后面next指向空指针了

 之后将cur->next指向pre，然后将cur和pre向后移动

 此时移动next之前要判断是否，为空

则返回当前头指针pre即可 

struct ListNode* reverseList(struct ListNode* head){    //判断head和head->next是不是空，防止空指针    if(head == NULL){ return NULL;    }    struct ListNode* pre = NULL;    struct ListNode* cur = head;    struct ListNode* next = head->next;    while(cur != NULL){ cur->next = pre; pre = cur; cur = next; //next是不是空，防止空指针 if(next != NULL){     next = next->next; }    }    return pre;}

🔑思路2：

 

创建一个新的头指针 newhead，将cur指向newhead，再将newhead移动到cur，将cur移动到next，移动next之前要判断是否为空

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

🌏三、链表的中间节点 （传送门）

🍤给定一个头结点为 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.

 🔑思路：

        运用快慢指针，将两个指针都从head开始，然后直到fast或者fast->next指向为空就找到了中间的节点了，注意，判断的时候，要注意fast->next要在fast之后，防止空指针

struct ListNode* middleNode(struct ListNode* head){    struct ListNode* fast = head;    struct ListNode* slow = head;    //不能换位置，从左往右先判断,否则判断为空指针    while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next;    }    return slow;}

🌏四、链表中倒数第K个节点（传送门）

 🍤输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

🔑思路：

        依旧是利用快慢指针，首先，让fast移动K为，然后fast和slow之间的距离就是K，然后同时走，当fast为空的时候，slow指向的空间就是所求空间

struct ListNode* getKthFromEnd(struct ListNode* head, int k){    //如果是空则返回空    if(head == NULL){ return NULL    }    struct ListNode* fast = head;    struct ListNode* slow = head;    while(k--){ fast = fast->next;    }    while(fast != NULL){ fast = fast->next; slow = slow->next;    }    return slow;}

 🌏五、合并两个有序链表（传送门）

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

示例 1：

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

 🔑思路1：

        取一个初始为空的新链表，比较指向list1和指向list2的节点值，小的先放入新链表，之后，小的节点指针向后移动。当有一个指针为空时，就将另一个链表直接连接至新链表之后。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){    //分别判断list1和list2是否为空    if(list1 == NULL){ return list2;    }    if(list2 == NULL){ return list1;    }    struct ListNode* head = NULL;    struct ListNode* tail = NULL;    while(list1 != NULL && list2 != NULL){ if(list1-> val  val){     //判断头是不是空     if(tail == NULL){  head = tail = list1;     }else{  tail->next = list1;  tail = list1;     }     list1 = list1->next; }else{     if(tail == NULL){  head = tail = list2;     }else{  tail -> next = list2;  tail = list2;     }     list2 = list2->next; }    }    //遍历完后有判断是否还有没有遍历的    if(list1 != NULL){ tail->next = list1;    }    if(list2 != NULL){ tail->next = list2;    }    return head;}

  🔑思路2：

        思路1是不带哨兵的，下面写一个带哨兵的

        由于创建哨兵，所以不用判断list1和list2是否为空了，因为我们的返回值是head->next,返回的是头，而不是哨兵。

        最后记得释放内存

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){    //带哨兵位    struct ListNode* head, *tail;    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));    head->next = NULL;    while(list1 != NULL && list2 != NULL){ if(list1-> val  val){     tail->next = list1;     tail = list1;     list1 = list1->next; }else{     tail -> next = list2;     tail = list2;     list2 = list2->next; }    }    //遍历完后有判断是否还有没有遍历的    if(list1 != NULL){ tail->next = list1;    }    if(list2 != NULL){ tail->next = list2;    }    //为方便释放内存，提前记录头    struct ListNode* list = head->next;    free(head);    //返回哨兵位下一位    return list;}

 🌏六、链表分割（传送门）

🍤给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：

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

🔑思路： 

        新链表less和新链表greater，它们初始都为空。然后用指针cur遍历一遍原链表，小于x的节点放入less链表中，大于x的放入greater链表中，最后再将less和greater连接起来，返回less的头指针

        当less不为空时，less最后的节点要指向greater的头节点。并且将greater最后节点的指针指向空。因为greater最后的指向可能指向less的某个节点，连接less和greater的时候就会形成死循环

struct ListNode* partition(struct ListNode* head, int x){    //less和greter分别为小于val和大于val的头指针    struct ListNode* lesshead,  *lesstail, *greterhead, *gretertail;    lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));    greterhead = gretertail = (struct ListNode*)malloc(sizeof(struct ListNode));    //初始化    lesstail->next = gretertail->next = NULL;    struct ListNode* cur = head;    while(cur != NULL){ if(cur->val next = cur;      lesstail = lesstail->next; }else{     gretertail->next = cur;     gretertail = gretertail->next; } cur = cur->next;    }    lesstail->next = greterhead->next;    //防止死循环    gretertail->next = NULL;    struct ListNode* list = lesshead->next;    //防止内存泄漏    free(lesshead);    free(greterhead);    return list;}

 🌏七、链表回文（传送门）

🍤给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

 🔑思路：

        找到中间节点，将它逆置之后，分别从head和rhead开始比较。

偶数情况：

 奇数情况：

 结果都一样，要注意的是反转之后，rhead节点的前一个指向的是rhead最后一个

//找中间节点struct ListNode* middleNode(struct ListNode* head){    struct ListNode* fast = head;    struct ListNode* slow = head;    //不能换位置，从左往右先判断,否则判断为空指针    while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next;    }    return slow;}//逆置struct ListNode* reverseList(struct ListNode* head){    if(head == NULL){ return NULL;    }    struct ListNode* cur = head;    struct ListNode* next = cur->next;    struct ListNode* newhead =NULL;    while(cur != NULL){ cur->next = newhead; newhead = cur; cur = next; if(next!=NULL){     next = next->next;  }    }    return newhead;}bool isPalindrome(struct ListNode* head){    struct ListNode* midhead = middleNode(head);    struct ListNode* rhead = reverseList(midhead);    while(head != NULL && rhead != NULL){ if(head->val != rhead->val){     return false; } head = head->next; rhead = rhead->next;    }    return true;}

 🌏八、相交链表（传送门）

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

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

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

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

输入：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 个节点。

  🔑思路：

        先算出listA和listB长度，然后两个链表中较长的先走两者长度的差值，此时长的链表现在长度和短的一样，之后遍历如果发现相等则返回。

 注意：编译器只会检查语法逻辑，执行逻辑不会检查，所以按照语法，我们要加上return，尽管没有返回从逻辑上来说

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {    struct ListNode* tailA = headA;    struct ListNode* tailB = headB;    //第一个节点跳过，所以长度从一开始    int lenA = 1;    int lenB = 1;    while(tailA->next != NULL){ tailA = tailA->next; lenA++;    }    while(tailB->next != NULL){ tailB = tailB->next; lenB++;    }    //尾节点是否相同    if(tailA != tailB){ return NULL;    }    //相交求交点，长的先走差值的步数，再一起走    struct ListNode* shortlist = headB;    struct ListNode* longlist = headA;    if(lenA next;    }    while(shortlist != NULL && longlist != NULL){ if(shortlist == longlist){     return longlist; } longlist = longlist->next; shortlist = shortlist->next;    }    //执行逻辑没有问题，但是没有返回值的话会有语法逻辑    return NULL;}

🌏九、 环形链表（传送门）

 🍤给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

🔑思路：

        快慢指针，如果在一个链表中，fast和slow能够相等，说明能找到，没有找到就说明没有环

bool hasCycle(struct ListNode *head) {    struct ListNode *slow = head;    struct ListNode *fast = head;    while(fast && fast->next){ slow = slow->next; fast = fast->next->next; if(slow == fast){     return true; }    }    return false;}

 🌏环形指针扩展

🍤如果fast一次走两步，slow一次走一步，它们一次会相遇吗？

        一定能！每次fast追击后，fast和slow距离减一

🍤如果fast一次走3步，slow一次走1步，它们一次会相遇吗？

        不一定，当两者距离是偶数一定能追上，因为每次fast和slow距离减少2，如果是奇数不行，fast会越过slow

🍤如果fast一次走4步，slow一次走一步，它们一次会相遇吗？

        一样的，只有fast和slow之间的距离是fast每次移动和slow缩小距离的整数倍就能

 🌏十、环形链表||（传送门）

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

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

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

🔑思路：

        先用快慢指针判断是否，有环，又环的话就记录快慢指针相遇的节点

设【链表头--入口点】L

【入口点--相遇点】X

【环的长度】C

 慢指针走的路程为：L+X。

快指针走的路程为：L+X+C*N（其中N代表圈数，N>=1）。

快指针路程是慢指针路程的两倍

所以：L+X+C*N=2*(L+X)。（当L=10，C=2可以验证）

化简得：L=C*N-X

               L=C*(N-1)+(C-X)

计算得出：

一个指针从head走，另一个指针从meet走，当两指针相等时，它们就指向环的入口点

struct ListNode *detectCycle(struct ListNode *head) {    struct ListNode *slow = head, *fast = head;    while(fast && fast->next){ slow = slow->next; fast = fast->next->next; if(slow == fast){     struct ListNode *meet = slow;     //当meet和head相等的时候就是入口点     while(meet != head){  meet = meet->next;  head = head->next;     }     return head; }    }    return NULL;    }

 🌏十一、复制带随机指针的列表（传送门）

🍤例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

🔑思路：

        1.拷贝链表的每一个节点，将每个拷贝好的节点放在原节点后面

        2.将copy中的random变得和原节点一样

        3.拆解链表，把拷贝的链表从原链表中拆解出来

struct Node* copyRandomList(struct Node* head) {//1.拷贝链表并且将它放在原节点后面    struct Node* cur = head;    while(cur != NULL){ struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->next = cur->next; cur->next = copy; copy->val = cur->val; cur = cur->next->next;    }    //2.将copy中random变为原节点一样    cur = head;    while(cur != NULL){ struct Node* copy = cur->next; if(cur->random == NULL){     copy->random = cur->random; }else{     copy->random = cur->random->next; } cur = cur->next->next;    }    //3.解开链表，构成原节点    struct Node* copyhead = NULL, *copytail = NULL;    cur = head;    while(cur != NULL){ struct Node* copy = cur->next; struct Node* next = copy->next; if(copyhead == NULL){     copyhead = copytail = copy; }else{     copytail->next = copy;     copytail = copy; } cur->next = next; cur = next;    }    return copyhead;}

🌏总结

字体下载