💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
876.链表的中间节点
题目要求:
| 给你单链表的头结点 head ，请你找出并返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 |
示例 1：
输入：head = [1,2,3,4,5]
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4，返回第二个结点。
思路：
1.定义快指针和慢指针
2.快指针一次走两步，慢指针一次走一步，
3.快指针走到链表最后时，快指针所走的距离正好是慢指针的二倍。
代码实现：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode* low = head; struct ListNode* fast = head; while(fast && fast->next) { low = low->next; fast = fast->next->next; } return low; }
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.如果head一开始就是空，或者，进行N次头删之后，为空。就返回head
3.中间的节点正常删除。尾删与之一样。
代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { while(head && head->val == val) head = head->next; //排除第一个节点就相等的情况 if(!head) //如果删除第一个，判断是否就空了 return head; struct ListNode* slow = head; //定义快慢指针，也要写在上一步之后 struct ListNode* fast = head->next; while(fast) { if(fast->val==val) { //遇到相等就删除 slow->next = fast->next; fast = slow->next; } else { //否则快慢指针依次后移 slow = slow->next; fast = fast->next; } } return head; }
牛客题—链表中倒数第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 = pListHead; struct ListNode* low = pListHead; int i = k-1; //判断是否为空，或这k有问题 if(pListHead==NULL||k<=0) return NULL; while(i--) { if(fast->next==NULL) { return NULL; } fast = fast->next; } //两个指针开始同时移动，到最后low表示倒数k的节点 while(fast->next) { low = low->next; fast = fast->next; } return low; }
答案正确！
注意：在测试样例中我发现个问题。
倒数第五个不应该是1吗？
原因是，fast后移k-1个，此时fast指针已经指向最后一个元素（fast->next==NULL),所以，根本就没有进行while循环，两个指针同步移动中去。又因为我们最开始给 low= =plisthead，所以，此时返回的是整个链表。
反转链表
头插法：
思路：
从头开始取链表的每一个节点插入到newnode之前
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* cur = head; struct ListNode* newnode = NULL; //头插 while(cur) { //定义一个之指针用来保存下一个节点 struct ListNode* tmp = cur->next; cur->next = newnode;//头插 newnode = cur;//将newnode指针前移 cur = tmp; } return newnode; }
cm11-链表分割
描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：
代码：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* ghead,* gtail,* lhead,* ltail; lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode)); ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = pHead; //遍历链表，大于等于x的放ghead链表中，小于x的放lhead链表 while(cur) { if(cur->val >= x) { gtail->next = cur;//尾插 gtail = gtail->next;//移向下一位 } else { ltail->next = cur;//尾插 ltail = ltail->next; } cur = cur->next; } ltail->next = ghead->next; gtail->next = NULL; struct ListNode* head = lhead->next; free(lhead); free(ghead); return head; } };
