链表刷题笔记(较难篇) (c实现)(跑路人笔记)

文章目录

前言

本篇包含牛客两道较难题和部分简单题,前面的简单题有为后面的难题做铺垫
前两道题是为第三道较难题做铺垫
对了前面两道题我之前有篇博客写了所以我直接沾过来了=-=.
然后好像被检测啥的了我弄成自己可见了=-=大家见谅.🙃
要是感觉有不懂的可以私聊或评论我,我马上改👍

翻转单链表–力扣简单👍

正确代码

/**
 * 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) {}
};*/classPalindromeList{public:boolchkPalindrome(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{returnfalse;}}returntrue;}};

讲解

我们这道题的思路是先通过快慢指针找到链表的中间节点,然后通过三个指针进行中间节点后的逆置,最后再通过遍历进行比较
整体思路的时间复杂度为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. 1->2->3->NULL
2. 1->2->3->NULL 这时无论以谁为结束条件都可👍

非回文的情况
直接在后续循环里的else判断去除了👍.
这样一道难题就解决了🤪.

结尾

舒文想要机器人,呜呜呜呜呜😭😭.