💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
- 876.链表的中间节点
- 203.移除链表元素
- 牛客题---链表中倒数第k个结点
- 反转链表
- cm11-链表分割
- 链表的回文结构
876.链表的中间节点
题目要求:
给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 |
输入: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 herestruct 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 herestruct 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;}
};
链表的回文结构
题目:对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例: 1->2->2->1 返回:true
思路:
1.找到中间节点
2.从中间节点往后逆置
3.定义快慢指针,向后遍历判断是否相等。
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow = head,*fast = head;while(fast&& fast->next){slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reveseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* newhead = nullptr;while(cur){struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;} return newhead;} bool chkPalindrome(ListNode* head) {// write code herestruct ListNode* mid = middleNode(head);struct ListNode* rmid = reveseList(mid);while(rmid && head){if(rmid->val !=head->val){return false;}rmid = rmid->next;head = head->next;}return true;}
};