上文回顾---单链表
这章将来做一些链表的相关题目。
目录
1.移除链表元素
2.反转链表
3.链表的中间结点
4.链表中的倒数第k个结点
5.合并两个有序链表
6.链表分割
7.链表的回文结构
8.相交链表
9.环形链表
编辑
10.环形链表II
编辑 编辑
1.移除链表元素
思路:我们可以通过循环链表,判断结点的val与给出的val是否一致,一致则跳过该结点即可;
由于我们是跳过某个结点,那么就会让这个结点的上一个结点和下一个结点进行关联;所以我们以某结点的next的val去判断;所以对于头结点来说,我们还要创建一个结点连接着头结点;
我们自己创建一个结点,还可以规避头指针为空的问题;
答案:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//哨兵位
struct ListNode* newhead=malloc(sizeof(struct ListNode));
newhead->next=head;
struct ListNode* cur=newhead;
while(cur->next)
{
//判断下一个的值
if(cur->next->val==val)
{
cur->next=cur->next->next;
}
else{
cur=cur->next;
}
}
//返回头指针
return newhead->next;
}
2.反转链表
思路:这道题实际上就是让结点的next改变即可;
所以在这里,我们创建3个指针prev,cur,next,让cur的next指向prev,然后进行指针移动,循环往复;一开始的prev指向NULL;如果head为空,那么就特殊处理,直接返回空;
答案:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//特殊条件
if(head==NULL)
{
return NULL;
}
struct ListNode* cur=head;
struct ListNode* prev=NULL;
struct ListNode* next=head->next;
//移动指针
while(cur)
{
cur->next=prev;
prev=cur;
cur=next;
//判断next
if(next!=NULL)
{
next=next->next;
}
}
return prev;
}
3.链表的中间结点
思路1:我们可以先算出链表的总长度,然后再取中间结点的位置;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
//先确定链表长度
int i=0;
struct ListNode* node=head;
while(node!=NULL)
{
node=node->next;
i++;
}
//确定中间节点位置
int k=i/2;
for(int i=0;i<k;i++)
{
head=head->next;
}
return head;
}
思路2:利用快慢指针的思想;
我们只有在链表遍历到为NULL才知道结束,那么我们是否可以利用当指针到达末尾时就知道中间位置的思想呢?
这里我们用到的快慢指针思想就可以解决该问题,利用它们的速度差,走到的长度就是不一样的;
快指针一次跨越2个结点,而慢指针一次跨越1个结点,等到快指针到达末尾时,慢指针刚好到达中间位置;
对于两个中间结点的,我们需要让快指针走到NULL才能达到第二个结点;而一个中间结点的,只需要让快指针走到最后一个结点即可;
答案:
struct ListNode* middleNode(struct ListNode* head){
//快慢指针
struct ListNode* slow,*fast;
slow=fast=head;
//移动
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
4.链表中的倒数第k个结点
思路:这里还是利用到快慢指针的思想;还是利用快指针到达末尾,然后得知结点的思路;
只不过这里利用的是快慢之间的相对距离,上一题是快慢之间的相对速度;
我们可以让fast指针先走k步,然后在让slow和fast同时走,那么当fast指针到达NULL时, slow刚好到达返回的结点;
这里要注意的几个特殊情况:头指针为空;k的大小超过链表长度;
答案:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
if(pListHead==NULL)
{
return NULL;
}
//利用相对距离
struct ListNode* slow,*fast;
slow=fast=pListHead;
//先走k步
while(k&&fast)
{
fast=fast->next;
k--;
}
if(k>0)
{
return NULL;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
5.合并两个有序链表
思路:这里我们先创建一个结点,通过判断两链表的头结点的val大小,来决定连接着哪个;
然后循环遍历,移动指针,执行同样的操作;
当某一链表结束了,需要链接另一条链表剩余的结点;
答案:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//哨兵位
struct ListNode* prehead=malloc(sizeof(struct ListNode));
//比大小
struct ListNode* prev=prehead;
while(list1&&list2)
{
if(list1->val<list2->val)
{
prev->next=list1;
list1=list1->next;
prev=prev->next;
}
else
{
prev->next=list2;
list2=list2->next;
prev=prev->next;
}
}
//判断哪个链表有剩余
prev->next=list1==NULL?list2:list1;
return prehead->next;
}
6.链表分割
思路:我们可以创建2个结点,第一个结点连接着比x小的结点,第二个连接着>=x的结点;
最后将着两个新链表连接在一起;
这里要注意,最后的结点要接空,否则该结点的next保持不变,可能会造成环,将会报错;
答案:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* prevHead1=(struct ListNode*)malloc(sizeof(ListNode));
struct ListNode* prevHead2=(struct ListNode*)malloc(sizeof(ListNode));
ListNode* tail1=prevHead1;
ListNode* tail2=prevHead2;
while(pHead)
{
if(pHead->val<x)
{
tail1->next=pHead;
tail1=tail1->next;
}
else {
tail2->next=pHead;
tail2=tail2->next;
}
pHead=pHead->next;
}
//连接
tail1->next=prevHead2->next;
//尾置空
tail2->next=NULL;
return prevHead1->next;
}
};
7.链表的回文结构
思路:这里我们没有办法从后走向前,单链表是单向的;所以我们可以只能从前往后走;
我们可以先找到中间结点,然后对中间结点之后的链表进行倒转,最后通过中间指针和头指针遍历,判断对应的val是否相同即可;
答案:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head){
//快慢指针
struct ListNode* slow,*fast;
slow=fast=head;
//移动
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head){
//特殊条件
if(head==NULL)
{
return NULL;
}
struct ListNode* cur=head;
struct ListNode* prev=NULL;
struct ListNode* next=head->next;
//移动指针
while(cur)
{
cur->next=prev;
prev=cur;
cur=next;
//判断next
if(next!=NULL)
{
next=next->next;
}
}
return prev;
}
bool chkPalindrome(ListNode* head) {
ListNode* mid=middleNode(head); //找中间
ListNode* rmid=reverseList(mid); //中间位置后面倒置
//比较
while(rmid)
{
if(head->val!=rmid->val)
{
return false;
}
head=head->next;
rmid=rmid->next;
}
return true;
}
};
8.相交链表
思路:我们要看作是两条链表,然后后半部分连接是相同部分的结点;
会发现相交的链表的相交部分都是一样的;我们可以利用它们的尾结点来判断是否相交;
对于没有相交的部分,我们无法确保它们的长度;所以我们可以先让比较长的链表先走长度差,然后再一起访问;当访问的结点一致时,表明找到了相交的第一个结点;
答案:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenthA=1,lenthB=1;
struct ListNode* curA=headA;
struct ListNode* curB=headB;
//计算链表长度
while(curA->next)
{
++lenthA;
curA=curA->next;
}
while(curB->next)
{
++lenthB;
curB=curB->next;
}
//尾节点判断,不一样说明没有香蕉
if(curA!=curB)
{
return NULL;
}
//长度先走差距步
struct ListNode* longList=headA,*shortList=headB;
int abs=fabs(lenthA-lenthB);
if(lenthA<lenthB)
{
longList=headB;
shortList=headA;
}
while(abs--)
{
longList=longList->next;
}
//找到相同的交点
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
这里要注意,curA,curB只能走到尾结点,目的是为了判断它们是否相同,是否相交;
9.环形链表
思路:还是利用快慢指针的思想;
假设有环,通过快慢指针, 快指针一定先进入环中,当慢指针进入环时,让快指针去追逐慢指针;
如果快指针走到了空,表示没有环;
这里我们让快指针走两步,让慢指针走1步;当慢指针进入环时,假设快指针到慢指针距离为N,那么没走一次,它们之间的距离就会减1,直至减到N为0,表示快指针追到了;
答案:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
//快慢指针
//赛道追逐问题
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
return true;
}
}
return false;
}
这里为什么不让快指针走3步,让慢指针走1步呢?
假设慢指针进入循环后它们之间距离为N
每走一次,它们之间的距离就会减2,N-2,N-4……
如果N为偶数,那么减到最后可以为0,那么就表示追上了,
而如果N为奇数,那么追到最后为1或者-1,不是差一点追上,就是追过了,所以它们的相遇还要考虑环的周长,追过了距离就变为周长-1;
到最后,可能追上了,可能一直遇不到;
例如:
当slow在左边,fast就在右边;slow在右边,fast就在左边;永远都遇不到;
所以为了方便解决问题,就让快指针走2步即可;
10.环形链表II
思路:这里我们要在第9题的思想上再引入数学的思想;
假设起点到环入口距离为L,环周长为C,入口到相遇点距离X;
fast指针走的距离是slow指针的2倍,所以fast指针会先进入环中, fast可能会在环中绕几圈,我们设为n;
那么slow指针走的距离为L+X;
fast指针走的距离为L+n(n>=1)*C+X,fast指针要追上slow,至少要绕一圈环;
那么通过它们之间的关系
得到2(L+X)=L+n*C+X
最终得到L=(n-1)*C+C-X;
也就是说,L的距离会等于n圈环的周长加上相遇点到入口的距离;
那么将得出结论:
一个指针从起点走,一个指针从相遇点走,它们将会在入口点相遇;
答案:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
//快慢指针
struct ListNode* fast,*slow;
fast=slow=head;
//有环
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
//相遇点
if(fast==slow)
{
struct ListNode* meet=fast;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return NULL;
}
通过分析之后,我们不需要管那些未知数;
假设L很长,环很小,那么在相遇点的指针就会在环中多走几圈;
假设L很短,那么相遇点到入口点的距离就刚好是L的长度;文章来源:https://www.toymoban.com/news/detail-634404.html
所以在写代码中,我们只需要知道起始的指针和相遇点的指针最终会相遇,且就是入口点。文章来源地址https://www.toymoban.com/news/detail-634404.html
到了这里,关于数据结构--单链表OJ题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!