前言
本篇包含牛客两道较难题和部分简单题,前面的简单题有为后面的难题做铺垫
前两道题是为第三道较难题做铺垫
对了前面两道题我之前有篇博客写了所以我直接沾过来了=-=.
然后好像被检测啥的了我弄成自己可见了=-=大家见谅.🙃
要是感觉有不懂的可以私聊或评论我,我马上改👍
翻转单链表–力扣简单👍
正确代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur!=NULL) { struct ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }
思路
我的思路是将链表的指针进行翻转
比如:
要翻转这个链表
我们就要知道链表的上一位,下一位
然后让当前的链表内容的next指向上一位,然后通过next变量向下移动链表当当前内容为NULL时停止循环.
所以这道题只需要三个变量就可以解决问题=-=.
链表的中间节点–力扣简单👍
连接
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
正确代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { assert(head); struct ListNode* slow = head; struct ListNode* fast = head; while(fast!=NULL&&fast->next!=NULL) { slow = slow->next; fast = fast->next->next; } return slow; }
讲解
使用快慢指针,慢指针向后走一步的时候快指针走两步就好了=-=.
思路很简单但是其实还挺难想的=-=.
链表的回文结构(牛客较难)🤦♂️
连接
回文结构:
指逆置后和正序一致的数据如1221逆置后还是1221所以1221为true
再如123 逆置后为321 就不为回文结构.
不得不说一句,牛客的题目描述和报错实在是做的一般般🤦♂️.
今天不小心调用了空指针他直接给我个段报错实在是难受🤦♂️.
不小心发了点牢骚=-=.我们继续
正确代码
提醒一下虽然这是C++形势的代码但是内部都是C写的所以大家不用被劝退💕
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool chkPalindrome(ListNode* A) { ListNode*fast=A ,*slow=A,*cur=NULL,*next=NULL,*prev=NULL; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; } next = slow->next; prev = NULL; cur = slow; while(cur) { cur->next = prev; prev = cur; cur = next; next = next->next; } ListNode* newhead1 = A; ListNode* newhead2 = prev; while(newhead2) { if(newhead1->val ==newhead2->val) { newhead1 = newhead1->next; newhead2 = newhead2->next; } else { return false; } } return true; } };
讲解
我们这道题的思路是先通过快慢指针找到链表的中间节点,然后通过三个指针进行中间节点后的逆置,最后再通过遍历进行比较
整体思路的时间复杂度为O(N)空间复杂度为O(1)符合题目要求👍
while(fast&&fast->next) { fast = fast->next->next; slow
= slow->next;
}
寻找中间节点通过快慢指针.
next = slow->next; prev = NULL; cur = slow; while(cur) { cur->next = prev; prev = cur; cur = next; next = next->next; }
逆序后面部分的链表内容
ListNode* newhead1 = A; ListNode* newhead2 = prev; while(newhead2) { if(newhead1->val == newhead2->val) { newhead1 = newhead1->next; newhead2 = newhead2->next; } else { return false; } } return true; }
在赋值时我将A给newhead1我相信大家都能理解
把prev赋值给newhead2是将逆序后的头给newhead2👍
比较逆序后的部分,以newhead2为循环的终止条件
分为三种情况
正常情况如1221
中间为对称点情况12321
非回文情况1212
正常情况如1221下的newhead2应该在1221的第三个元素的位置及2的位置
这部分已经为逆置过的情况所以情况现在应该从1221变为两个1->2->2->NULL(注:这部分没错,在逆序时我们的第一个链表确实是这种情况,因为我们是将第三个元素的next置为空的👍)
第二个链表情况应该为1->2->NULL而我们的第一个链表.所以我们只需要比较从第二个链表的头到NULL即可👍.
中间为对称点的情况
及12321时也是因为逆序分成了两个链表
1->2->3->NULL
1->2->3->NULL
这时无论以谁为结束条件都可👍
非回文的情况
直接在后续循环里的else判断去除了👍.
这样一道难题就解决了🤪.
结尾
舒文想要机器人,呜呜呜呜呜😭😭.
