数据结构力扣OJ题
目录
本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵!
题一:链表分割
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
思路一:
1.分别创建一个记录小于x的“小”结构体,和记录大于等于x的“大”结构体,
2.然后malloc函数动态开辟一个结构体大小的空间,这时head和tail都指向同一位置,将phead->val与x比较,小于想,放入less中,大于等于x放入great中,
3.当phead为NULL时,将两个“大”“小”结构体链接起来,记录lesshead节点,然后free释放开辟的动态内存空间,返回记录lesshead的地址。
-
ListNode* partition(ListNode* phead, int x)
-
{
-
-
struct ListNode* head = phead ;
-
struct ListNode* lesshead ;
-
struct ListNode* greathead ;
-
struct ListNode* lesstail ;
-
struct ListNode* greattail ;
-
//动态开辟空间
-
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
-
greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
-
-
while(head)
-
{
-
//小于x的尾插到lessTail
-
if(head->val < x)
-
{
-
lesstail->next = head;
-
lesstail = lesstail->next;
-
}
-
//大于等于x的尾插到greaterTail
-
else
-
{
-
greattail->next = head;
-
greattail = greattail->next;
-
}
-
//下一个位置
-
head = head->next;
-
}
-
//小的接上大的
-
lesstail->next = greathead->next;
-
greattail->next = NULL;
-
-
//新头节点
-
struct ListNode* Phead = lesshead->next;
-
//销毁
-
free(lesshead);
-
free(greathead);
-
-
-
return Phead;
-
}
题二:相交链表
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
思路一:
1.先分别将A和B遍历一遍,计算出长度len
2.计算长度差Slen,让长的先指向Slen个next位置
3.此时再同时遍历,直到A和B的地址相同,
4.返回的就是第一个交点
-
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
-
{
-
struct ListNode* curA = headA,*curB = headB;
-
int len1 = 1,len2 = 1;
-
//计算链表长度
-
while(curA)
-
{
-
curA = curA->next;
-
len1 ;
-
}
-
while(curB)
-
{
-
curB = curB->next;
-
len2 ;
-
}
-
//如果此时遍历结束地址不相等,说明没有相交点
-
if(curA != curB)
-
{
-
return NULL;
-
}
-
//abs是计算差值绝对值函数
-
int Slen = abs(len1 - len2);
-
//二次遍历的长短链表
-
struct ListNode* longlist = headA,*shortlist = headB;
-
if(len1 < len2)
-
{
-
longlist = headB;
-
shortlist = headA;
-
}
-
//让longlist和shortlist的长度相同
-
while(Slen--)
-
{
-
longlist = longlist->next;
-
}
-
//找到第一个交点
-
while(longlist != shortlist)
-
{
-
longlist = longlist->next;
-
shortlist = shortlist->next;
-
}
-
//输出交点地址
-
return longlist;
-
}
题三:环形链表
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
示例 1:
思路一:
快慢指针思路:
1.创建快慢指针fast和slow;
2.开始位置相同,slow每次指向下一个地址, fast每次指向下下个地址;
3.循环判断,直到slow=fast地址相同;
4,相同则说明链表存在环;
反之,fast或fast->next尾NULL则不存在环。
-
bool hasCycle(struct ListNode *head)
-
{
-
struct ListNode* slow = head;
-
struct ListNode* fast = head;
-
//fast或fast->next尾NULL则不存在环
-
while(fast && fast->next)
-
{
-
//slow每次指向下一个地址, fast每次指向下下个地址
-
slow = slow->next;
-
fast = fast->next->next;
-
//相同则说明链表存在环
-
if(slow == fast)
-
{
-
return true;
-
}
-
}
-
-
return false;
-
}
题四:链表的回文结构
思路一:
如下:两种方法,得到的节点去循环判断,如果newnode或者head一个为NULL,则说明是回文结构,如果在循环中结束·,则不是回文结构。
链表反转:
三个变量n1=NULL,n2=head,n3,如果n2不为NULL,则n3=n2->next,循环如果n2为NULL,就停下来,当n3为空时n3就不进行变化,最后n1会停在最后一个位置,这个时候逆置完成。
查找中间节点:
分别定义快慢两个指针,快指针一次前进两个地址,慢指针一次前进一个地址,当奇数时快指针的next为NULL时,当链表为偶数时判断条件为地址为NULL,停下来,此时慢指针就在链表中间节点上。
-
//将链表反转
-
struct ListNode* reverseList(struct ListNode* head)
-
{
-
struct ListNode* n1,*n2,*n3;
-
n1 = NULL;
-
n2 = head;
-
if(n2)
-
n3 = n2->next;
-
-
while(n2)
-
{
-
n2->next = n1;
-
n1 = n2;
-
n2 = n3;
-
if(n3)
-
n3 = n3->next;
-
}
-
return n1;
-
}
-
//得到链表中间节点
-
struct ListNode* middleNode(struct ListNode* head)
-
{
-
struct ListNode* slow = head;
-
struct ListNode* fast = head;
-
while(fast && fast->next)
-
{
-
-
slow = slow->next;
-
fast = fast->next->next;
-
-
}
-
return slow;
-
}
-
class PalindromeList {
-
public:
-
bool chkPalindrome(ListNode* head)
-
{
-
struct ListNode* mid = middleNode(head);
-
struct ListNode* newnode = reverseList(mid);
-
//一个为空自己退出
-
while(newnode && head)
-
{
-
//不相同,则不是回文结构
-
if(newnode->val != head->val)
-
{
-
return false;
-
}
-
-
newnode = newnode->next;
-
head = head->next;
-
}
-
return true;
-
}
-
};
本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgghjai
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13