👉移除链表元素👈
给你一个链表的头节点 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
输出：[]
提示：
列表中的节点数目在范围 [0, 10^4] 内
1 <= Node.val <= 50
0 <= val <= 50
思路一
定义两个指针cur和prev，cur为当前节点的地址，prev为上一个节点的地址。
当cur->val == val且cur == head时，将头节点的下一个节点作为新的头节点，释放当前节点cur，cur重新赋值为head，此时的删除为头删。
当cur->val == val且cur != head时，将上一个节点prev的next赋值为当前节点cur的next，再将当前节点cur释放，cur重新赋值为prev->next，此时的删除为中间删。
当cur->val != val时，将prev赋值为cur记住当前节点的位置，方便后续删除节点，再将cur赋值为cur->next，迭代往后走。
/* * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *prev = NULL; struct ListNode *cur = head; while(cur) { //当前节点的值等于val if(cur->val == val) { //头删 if(cur == head) { head = head->next;//换头 free(cur);//释放头节点 cur = head;//迭代往后走 } //中间删 else { prev->next = cur->next;//前一个节点指向cur的下一个节点 free(cur);//释放当前的节点 cur = prev->next;//迭代往后走 } } //当前节点的值不等于val else { prev = cur;//prev记住当前节点的位置，方便后续删除节点 cur = cur->next;//迭代往后走 } } return head; }
思路二
定义一个三个变量，分别是哨兵位头节点DummyNode、当前节点cur和尾节点tail。利用while循环变量整个链表，当cur->val != val时，尾插数据到新链表中tail->next = cur, tail = cur, cur = cur->next；当cur->val == val时，删除节点并往后走struct ListNode* del, cur = cur->next, free(del)。循环结束后，尾节点指向NULL，防止野指针问题。最后，将哨兵位头节点释放掉，返回结果就行了。
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* DummyNode = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail = DummyNode; DummyNode->next = NULL; while(cur) { if(cur->val != val) { tail->next = cur; tail = cur; cur = cur->next; } else { struct ListNode* del = cur; cur = cur->next; free(del); } } tail->next = NULL; struct ListNode* newHead = DummyNode->next; free(DummyNode); return newHead; }
👉反转链表👈
给你单链表的头节点 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
思路一
取原链表中的节点，头插到newhead新链表中。需要借助几个变量才能完成这个过程：next记录当前节点cur的下一个节点；然后进行头插，将cur->next赋值为newhead
，让当前节点链接到要返回的链表中；再然后将newhead赋值为cur，更新头结点；最后将cur赋值为next，迭代往后走。
/* * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { //思路：取原链表中的节点，头插到newhead新链表中 struct ListNode* cur = head; struct ListNode* newhead = NULL; while(cur) { //next记录当前节点的下一个节点 struct ListNode* next = cur->next; //头插 cur->next = newhead; newhead = cur; //迭代往后走 cur = next; } return newhead; }
思路二
定义三个指针，分别是n1、n2和n3。n1记录的是上一个节点的地址，n2记录的是当前节点的地址、n3记录的是下一个节点的地址。现将n2->next赋值为n1进行反转链表；然后将n1赋值为n2，n2赋值为n3，n3赋值为n3->next进行迭代。
/* * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { //空链表 if(head == NULL) return NULL; struct ListNode* n1,*n2,*n3; n1=NULL;//记录上一个节点 n2=head;//记录当前节点 n3=head->next;//记录下一个节点 while(n2) { //反转 n2->next = n1; //迭代 n1 = n2; n2 = n3; //n3不为空才能解引用 if(n3!=NULL) { n3 = n3->next; } } return n1; }
👉链表的中间节点👈
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
思路：可以定义两个指针slow和fast，slow一次走一步，而fast一次走两步。当fast==NULL或者fast->next ==NULL 时，循环结束，此时的slow就是中间节点，将slow返回就行了。
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { slow = slow->next;//slow走一步 fast = fast->next->next;//fast走两步 } return slow; }
👉链表中倒数第k个节点👈
思路：定义两个指针slow和fast，先让fast先走k步，然后slow和fast一起走。当fast==NULL时，slow就是倒数第k个节点，将slow返回就行了。也可以让fast先走k-1步，然后slow和fast一起走，当fast==NULL时，slow就是倒数第k个节点。
/* * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* getKthFromEnd(struct ListNode* head, int k) { //fast先走k步，然后slow和fast一起走 //当fast==NULL时，slow就是倒数第k个节点 struct ListNode* slow = head; struct ListNode* fast = head; while(k--) { //k大于链表的长度 if(fast == NULL) { return NULL; } fast = fast->next; } while(fast) { slow = slow->next; fast = fast->next; } return slow; }
/* * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* getKthFromEnd(struct ListNode* head, int k) { //fast先走k-1步，然后slow和fast一起走 //当fast->next==NULL时，slow就是倒数第k个节点 struct ListNode* slow = head; struct ListNode* fast = head; while(--k) { //k大于链表的长度 if(fast == NULL) { return NULL; } fast = fast->next; } while(fast->next) { slow = slow->next; fast = fast->next; } return slow; }
以上两种方式均可解决这个问题，可以选择自己喜欢的一种。
👉总结👈
本篇博客讲解了几道的链表OJ题，其中涉及了链表的基本操作头插和中间插以及双指针的技巧。如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！💖💝❣️
