您现在的位置是:首页 >学无止境 >LeetCode刷题系列之----->(指针玩转链表篇)(三)网站首页学无止境

LeetCode刷题系列之----->(指针玩转链表篇)(三)

阿博历练记 2023-07-01 00:00:02
简介LeetCode刷题系列之----->(指针玩转链表篇)(三)

🍉博客主页:阿博历练记
📖文章专栏:数据结构与算法
🔍代码仓库:阿博编程日记
🌹欢迎关注:欢迎友友们点赞收藏+关注哦

在这里插入图片描述

🖋1.题目描述

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

💡 逻辑分析

在这里插入图片描述

📃哨兵位的概念

哨兵位的头结点不存储有效数据,是一个附加的链表节点,该节点作为第一个节点,它的值域不存储任何东西.只是为了操作的方便而引入的,如果一个链表有哨兵节点的话,那么线性表的第一个元素应该是链表的第二个节点.

❌错误案例(不带哨兵位)

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct  ListNode*lesshead=NULL,*lesstail=NULL,*graterhead=NULL,*gratertail=NULL;
        struct  ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
               if(lesstail==NULL)
               {
                 lesshead=lesstail=cur;
               }
               else 
               {
                  lesstail->next=cur;
                  lesstail=lesstail->next;
               }
            }
            else
            {
               if(gratertail==NULL)
               {
                graterhead=gratertail=cur;
               }
               else 
               {
                 gratertail->next=cur;
                 gratertail=gratertail->next;
               }
            }
            cur=cur->next;
        }
        lesstail->next=graterhead;
        return    lesshead;
 }
};

在这里插入图片描述

✔代码纠正

1.不带哨兵位

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct  ListNode*lesshead=NULL,*lesstail=NULL,*graterhead=NULL,*gratertail=NULL;
        struct  ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
               if(lesstail==NULL)
               {
                 lesshead=lesstail=cur;
               }
               else 
               {
                  lesstail->next=cur;
                  lesstail=lesstail->next;
               }
            }
            else
            {
               if(gratertail==NULL)
               {
                graterhead=gratertail=cur;
               }
               else 
               {
                 gratertail->next=cur;
                 gratertail=gratertail->next;
               }
            }
            cur=cur->next;
        }
        if(lesstail==NULL)
        return   graterhead;
        else
        {
        lesstail->next=graterhead;
        if(gratertail)
        gratertail->next=NULL;
        return    lesshead;
        }
 }
};

2.带哨兵位

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct  ListNode*lesshead,*lesstail,*graterhead,*gratertail;
        lesshead=lesstail=(struct  ListNode*)malloc(sizeof(struct ListNode));
        graterhead=gratertail=(struct  ListNode*)malloc(sizeof(struct ListNode));
        struct  ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                  lesstail->next=cur;
                  lesstail=lesstail->next;
            }
            else
            {
                 gratertail->next=cur;
                 gratertail=gratertail->next;
            }
            cur=cur->next;
        }
        lesstail->next=graterhead->next;
        gratertail->next=NULL;
        pHead=lesshead->next;
        free(lesshead);
        free(graterhead);
        return  pHead;
    }
};

友友们注意了,当我们用完哨兵位之后,我们要及时把它释放掉,返回链表新的头结点

🖋2.题目描述

在这里插入图片描述

📒 回文链表的概念(逻辑实现)

回文结构特征是正着读和反着读是一样的,因此我们只要找到链表的中间结点,再将链表的后半部分逆置,使用两个指针分别从头和中间结点开始遍历,如果在他们的next为空之前一直相等,说明该链表为回文结构

⭐疑问解析

在这里插入图片描述

🏆代码展示

class PalindromeList {
public:
 struct ListNode* reverseList(struct ListNode* head){
     struct  ListNode*cur=head;
     if(cur==NULL)
     {
         return  NULL;
     }
     struct  ListNode*rhead=NULL;
     struct  ListNode*next=cur->next;
     while(cur)
     {
     cur->next=rhead;
         rhead=cur;
         cur=next;
         if(cur)
         {
         next=cur->next;
         }
     }
     return  rhead;
}
struct ListNode* middleNode(struct ListNode* head){
     struct  ListNode*slow=head;
     struct  ListNode*fast=head;
     while(fast&&fast->next)
     {
         fast=fast->next->next;
         slow=slow->next;
     }
     return  slow;
}
bool chkPalindrome(ListNode* head){
     struct  ListNode*mid=middleNode(head);
     struct  ListNode*rmid=reverseList(mid);
     while(rmid)
     {
     if(rmid->val!=head->val)
        {
        return  false;
        }
        head=head->next;
        rmid=rmid->next;
     }
     return  true;
 }
 };

🖋3.题目描述

在这里插入图片描述

💡 逻辑分析

我们先求出链表A和链表B的长度L1和L2,使用双指针,并将他们对齐,即若A链表节点比B节点多n个,则将A的指针向后移动n个,B链表比A链表多时同理.保证剩余链表长度相同,然后在一起走,两个指针同步向后移动1个节点,要么同时找到第一个交点,要么都为NULL.

🏆代码展示

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int t1=0;
    int t2=0;
    struct  ListNode*p1=headA;
    struct  ListNode*p2=headB;
    if(p1==NULL||p2==NULL)
    return  NULL;
    while(p1)
    {
        t1++;
        p1=p1->next;
    }
    p1=headA;
    while(p2)
    {
        t2++;
        p2=p2->next;
    }
    p2=headB;
    if(t1>t2)
    {
    int temp=t1-t2;
       while(temp)
       {
           p1=p1->next;
           temp--;
       }
    }
    else
    {
        int  temp=t2-t1;
        while(temp)
        {
            p2=p2->next;
            temp--;
        }
    }
    while(p1&&p1!=p2)
    {
        p1=p1->next;
        p2=p2->next;
    }
    return  p1;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。