您现在的位置是:首页 >学无止境 >LeetCode刷题系列之----->(指针玩转链表篇)(三)网站首页学无止境
LeetCode刷题系列之----->(指针玩转链表篇)(三)
简介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;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。