• 【数据结构初阶】单链表补充内容+又双叒叕刷链表题

    目录

    1.顺序表&链表的优点和缺点

    2.单链表和双向循环链表

    3.一点杂七杂八的东西

    3-1顺序表和链表打印的断言

    3-2.栈上和堆上定义一个新节点 

    3-3.二级指针 

    3-4.哨兵头结点的作用

    3-5 为什么单链表的基本操作中无tail记录尾

    4.替换法删除pos结点

    4-1.变式

    5 .链表调试

    6.为什么学校老师讲的时候不先讲带头结点的

    7.刷刷刷题

    7-1.回文链表

    7-2.相交链表

    7-3. 链表分割

    1.顺序表&双向循环链表的优点和缺点

    顺序表：

    一.优点：

    1. 尾插尾删效率很高
    2. 支持用下标随机访问

    二.缺点：

    1. 头部和中部插入和删除效率低O(n)
    2. 扩容-----性能消耗+空间消耗

    双向循环链表：

    一.优点：

    1. 任意位置插入删除效率很高O(1)
    2. 按需申请释放

    二.缺点:

    1. 不支持随机访问

    综合而言，两个各有优缺，相辅相成，具体用谁看场景，但是总体而言顺序表使用的频率更高一点

    扩展一点：

    顺序表的cpu高速缓存命中率高（顺序表空间连续）

     

    2.单链表和双向循环链表

    1.单链表：其他结构的子结构（比如哈希桶），面试经常问到和OJ题目，且只适合头部的插入删除。

    2.双向循环链表：结构复杂，但是实现简单，最为实用，常被用于实际存数据，适合任意位置的插入删除。

    3.一点杂七杂八的东西

    3-1顺序表和链表打印的断言

    1. 1.顺序表和链表打印断言
    2.  
    3. 顺序表定义：SeqList Sq;
    4. 在传给打印函数的时候:SeqListPrint(&Sq)
    5. 在函数内部的时候&Sq一定不为空，void SeqListPrint(SeqList* ps)所以要断言一下assert(ps);
    6.  
    7. 单链表定义变量: SLTNode* phead;
    8. 在传给打印函数的时候:SLTNodePrint(&phead);
    9. 在函数内部打印的时候phead为空的时候，&phead也可能为空，所以不能断言

    但是注意：虽然phead为空，但是pphead不为空 ，所以在链表头插函数内部还是要对pphead断言。

    原因：phead没有指向任何内容，但是phead本身是一个指针变量，是变量就有地址。

     

    3-2.栈上和堆上定义一个新节点 

    1. 2.栈（错）和堆上（对）定义一个新节点
    2.  
    3. void SLTNodePushFront(SLTNode** pphead,STDateType x)
    4. {
    5.    //错误示范：栈上开辟的，出函数销毁
    6.    SLTNode newnode;
    7.  
    8.    //正确做法：malloc结点，堆上开辟，空间需要手动释放
    9.    SLTNode* newhead=(SLTNode*)malloc(sizeof(SLTNode));
    10. }

    3-3.二级指针 

    我们在主函数定义了SListNode*  plist;

    在改变plist的指向的时候就要传二级指针，但是如果在函数内改结点，直接用一级指针就能改，就像我们在函数内部定义的prev,cur等。这也就是哨兵位头结点的原理，在因为有哨兵位的头结点，就不用改plist，所以可以在主函数内传一级指针。

    1. 3.二级指针
    2.  
    3. 以尾插函数为例，如果主函数里的plist为空，那么要改plist就要传二级指针
    4. 但是为什么在plist不为空的时候，要尾插一个
    5.  
    6. void SLTNodePushBack(SLTNode* pphead, SLTDateType x)//1
    7. {
    8. 	assert(pphead);//2
    9.  
    10. 	SLTNode* newhead = (SLTNode*)malloc(sizeof(SLTNode));
    11. 	newnode->next = NULL;
    12. 	newnode->date = x;
    13.  
    14. 	if (*pphead == NULL)
    15. 	{
    16. 		*pphead = newnode;
    17. 	}
    18. 	else
    19. 	{
    20. 		SLTNode* tail = *pphead;
    21. 		while (tail)
    22. 		{
    23. 			tail = tail->next;
    24. 		}
    25. 		tail->next = newnode;//3
    26. 	}
    27. }

    无头单向不循环链表传二级指针发挥作用的情况：

    • 没有结点尾插
    • 只有一个结点尾删
    • 头插
    • 头删
    • 销毁

    3-4.哨兵头结点的作用

    头结点的作用：

    1. 方便对plist为空等特殊情况时的统一操作
    2. 避免传二级指针

    备注：有人说哨兵位头结点的数据域是用来存储单链表的长度；

    专业打假：其实这种说法是错误的，因为结点的数据域为char类型的且链表长度大于127的时候就会溢出，所以这种说法是错误的。

    3-5 为什么单链表的基本操作中无tail记录尾

    看过我写题的应该知道，在建立新链表的时候，通常是采用尾插操作，尾插相对于头插能够保证新链表的结点在原链表的相对顺序不变，但是尾插的缺点是每次尾插都要找尾，所以我们定义一个尾指针，实时更新尾指针。

    那为什么单链表的基本操作中无tail记录尾？那是因为在基本操作中不止有尾插，还有尾删，定义一个tail效果适用性不是很强。

    4.替换法删除pos结点

     

    基于单链表删除pos位置还要找尾的麻烦，删除pos位置的结点有一个替换法删除，数据域值交换的方法，时间复杂度是O(1):

    如果要删除pos位置的结点，则可以狸猫换太子把pos后面一个结点的值给pos位置的数据域，然后pos->next=pos->next->next,也就是把pos后面那个结点作替死鬼。

    缺点：pos位置不能是尾结点。

    pos位置是尾结点且链表是循环链表就可以，但是如果是循环链表的话就没必要使用替换法删除pos位置的结点.

    4-1.变式

    如果要在pos位置之前插入一个结点，时间复杂度为O(1),也可以采用这种方法：

    BuySListNode(pos->val);

    pos->val=x;

    5 .链表调试

    当OJ写不出来，想在VS上调试代码，找Bug，但是每次还要重建链表？有什么解决办法？

    备注：程序员一半的时间都在改Bug,你连调试都不会，就等着扣绩效吧😁😁

    解决办法：在桌面上备份一份单链表的代码，方便OJ调试。（代码如下）

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. struct  ListNode
    4. {
    5. 	int val;
    6. 	struct ListNode* next;
    7. };
    8.  
    9. #include
    10. #include
    11.  
    12.  
    13. int main()
    14. {
    15. 	struct  ListNode* n1 = (struct  ListNode*)malloc(sizeof(struct  ListNode)); 
    16. 	struct  ListNode* n2 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
    17. 	struct  ListNode* n3 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
    18. 	struct  ListNode* n4 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
    19. 	struct  ListNode* n5 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
    20. 	struct  ListNode* n6 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
    21. 	struct  ListNode* n7 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
    22.  
    23. 	n1->val = 1;
    24. 	n2->val = 2;
    25. 	n3->val = 3;
    26. 	n4->val = 4;
    27. 	n5->val = 5;
    28. 	n6->val = 6;
    29. 	n7->val = 7;
    30.  
    31. 	n1->next = n2;
    32. 	n2->next = n3;
    33. 	n3->next = n4;
    34. 	n4->next = n5;
    35. 	n5->next = n6;
    36. 	n6->next = n7;
    37. 	n7->next = NULL;
    38.  
    39. 	return 0;
    40. }

    6.为什么学校老师讲的时候不先讲带头结点的

    1. 实际应用中很少带头
    2. OJ题的head大大部分都是不带头的

    7.刷刷刷题

    上次的链表题刷的过瘾吗？链表习题集1

    我又双叒叕来了，记住题目是环环相扣的，记得先把习题集1做了哦，有些解法这里用到将不会再细讲...，敬请谅解 

    7-1.回文链表

    OR36 链表的回文结构

     思路1：

    1. 第一步：利用快慢指针找到链表的中间结点slow
    2. 第二步：将中间结点开始以后的结点部分逆置(反转），得到相交链表的新头指针prev
    3. 第三步：遍历判断两个链表是否值相等

    反转过程是最重要的部分，这里给出一点图理解一下

    1. class PalindromeList {
    2. public:
    3.     bool chkPalindrome(ListNode* phead) {
    4.         // 第一步：快慢指针求中间结点slow
    5.         struct ListNode* fast,*slow;
    6.         fast=slow=phead;
    7.         while(fast&&fast->next)
    8.         {
    9.             fast=fast->next->next;
    10.             slow=slow->next;
    11.         }
    12.         //第二步:部分反转,得新头结点prev
    13.         struct ListNode* prev=NULL;
    14.         struct ListNode* cur=slow;
    15.         while(cur)
    16.         {
    17.             struct ListNode* next=cur->next;
    18.             
    19.             cur->next=prev;
    20.             prev=cur;
    21.             cur=next;
    22.         }
    23.         //第三步：判断新旧链表是否相等
    24.         struct ListNode* newhead=prev;
    25.         struct ListNode* oldhead=phead;
    26.         while(newhead)
    27.         {
    28.             if(newhead->val!=oldhead->val)
    29.             {
    30.                 return false;
    31.             }
    32.             newhead=newhead->next;
    33.             oldhead=oldhead->next;
    34.         }
    35.         return true;
    36.     }
    37. };

    这里其实形参名是可以改成自己喜欢的名字，而不是题目这么挫的A 

    思路2：牢牢抓住回文链表的定义，从前往后和从后往前读都是一样的

    1. 第一步：拷贝原链表，得到头指针copyhead
    2. 第二步：将原链表整体反转,得到r头指针eversehead
    3. 第三步：遍历判断两个链表是否值相等

    （备注：这里一定一定要记得先拷贝一份原链表，否则反转后得到的链表将不再是原先那个链表！）

    1. class PalindromeList {
    2. public:
    3.     //动态开辟一个新节点，新节点的值为cur->val
    4.     struct ListNode* BuySListNode(int val)
    5.     {
    6.         struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    7.         newnode->val=val;
    8.         newnode->next=NULL;
    9.         return newnode;
    10.     }
    11.     
    12.     bool chkPalindrome(ListNode* phead) {
    13.         //第一步：拷贝原链表，得到copyhead
    14.         struct ListNode* Guard,*Tail;
    15.         Guard=Tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    16.         struct ListNode* cur=phead;
    17.         while(cur)
    18.         {
    19.             struct ListNode* next=cur->next;
    20.             
    21.             struct ListNode* newnode=BuySListNode(cur->val);
    22.  
    23.             Tail->next=newnode;
    24.             Tail=Tail->next;
    25.             cur=next;
    26.         }
    27.         struct ListNode* copyhead=Guard->next;
    28.         free(Guard);
    29.         Guard=NULL;
    30.         
    31.         //第二步：将原链表整体反转,得到reversehead
    32.         struct ListNode* prev=NULL;
    33.         struct ListNode* cur2=phead;
    34.         while(cur2)
    35.         {
    36.             struct ListNode* next=cur2->next;
    37.             cur2->next=prev;
    38.             prev=cur2;
    39.             cur2=next;
    40.         }
    41.         struct ListNode* reversehead=prev;
    42.         
    43.         //第三步：遍历判断两个链表是否值相等
    44.         while(copyhead)
    45.         {
    46.             if(copyhead->val!=reversehead->val)
    47.             {
    48.                 return false;
    49.             }
    50.             copyhead=copyhead->next;
    51.             reversehead=reversehead->next;
    52.         }
    53.         return true;
    54.     }
    55. };

    7-2.相交链表

    力扣之相交链表

    题目的相交链表可能有的同学会误以为是X字形，但是却只有Y字形，原因是每一个结点只有一个指针域，没有两个指针域。 

    思路：

    1. 第一步：分别遍历两个链表，分别求出两个链表的长度
    2. 第二步：让长度长的那个链表先走两链表长度的差距步
    3. 第三步：短链表从头开始走，长链表从差距步开始同步走
    4. 第四步：相遇点即是相交链表的交点结点，返回
    1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    2.     //第一步：分别遍历两个链表，分别求出两个链表的长度
    3.     int lenA=1,lenB=1;
    4.     struct ListNode* TailA=headA;
    5.     struct ListNode* TailB=headB;
    6.     while(TailA->next)
    7.     {
    8.         ++lenA;
    9.         TailA=TailA->next;
    10.     }
    11.     while(TailB->next)
    12.     {
    13.         ++lenB;
    14.         TailB=TailB->next;
    15.     }
    16.     if(TailA!=TailB)
    17.     {
    18.         return false;
    19.     }
    20.  
    21.     //第二步：让长度长的那个链表先走两链表长度的差距步
    22.     struct ListNode* longhead=headA;
    23.     struct ListNode* shorthead=headB;
    24.     if(lenA
    25.     {
    26.         longhead=headB;
    27.         shorthead=headA;
    28.     }
    29.     int div=abs(lenA-lenB);
    30.     struct ListNode* cur1=longhead;
    31.     struct ListNode* cur2=shorthead;
    32.     while(div--)
    33.     {
    34.         cur1=cur1->next;
    35.     }
    36.  
    37.     //第三步：短链表从头开始走，长链表从差距步开始同步走
    38.     while(cur1!=cur2)
    39.     {
    40.         cur1=cur1->next;
    41.         cur2=cur2->next;
    42.     }
    43.     //第四步：相遇点即是相交链表的交点结点，返回
    44.     return cur1;
    45. }

    7-3. 链表分割

    链表分割

    思路：将链表结点按数据值=x尾插到相应链表 ，然后再将两分割的链表连接起来。

    1. 第一步：定义大小Guard和Tail指针
    2. 第二步:   遍历尾插到相应新链表
    3. 第三步： 连接两个分割的链表

    备注：记得将bigTail->next置空！！！否则会运行超时

    1. class Partition {
    2. public:
    3.     ListNode* partition(ListNode* pHead, int val) {
    4.         // write code here
    5.         //第一步：定义大小Guard和Tail指针
    6.         struct ListNode* lessGuard,*lessTail;
    7.         lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    8.         lessGuard->next=NULL;
    9.         struct ListNode* bigGuard,*bigTail;
    10.         bigGuard=bigTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    11.         bigGuard->next=NULL;
    12.         
    13.         //第二步:   遍历尾插到相应新链表
    14.         struct ListNode* cur=pHead;
    15.         while(cur)
    16.         {
    17.             struct ListNode* next=cur->next;
    18.             if(cur->val
    19.             {
    20.                 lessTail->next=cur;
    21.                 lessTail=lessTail->next;
    22.             }
    23.             else 
    24.             {
    25.                 bigTail->next=cur;
    26.                 bigTail=bigTail->next;
    27.             }
    28.             cur=next;
    29.         }
    30.         //第三步： 连接两个分割的链表
    31.         lessTail->next=bigGuard->next;
    32.         bigTail->next=NULL;
    33.         struct ListNode* newhead=lessGuard->next;
    34.         free(lessGuard);
    35.         free(bigGuard);
    36.         lessGuard=NULL;
    37.         bigGuard=NULL;
    38.         return newhead;
    39.         
    40.     }
    41. };

  • 相关阅读:
    是什么引起数据库响应超时？
    请给出python程序运行结果
    从Github上整理下来的《Java面试神技》
    35、商户查询缓存（利用互斥锁解决缓存击穿）
    多线程JUC 第2季 synchronized锁升级过程
    Qt应用程序打包步骤（完美解决）
    ThreeDPoseTracker项目解析
    数字化时代，数据仓库是什么？有什么用？
    系统编程07-线程的互斥锁、读写锁、条件变量
    Appium入门自动化测试（4） —— Appium常用的手势操作API
  • 原文地址：https://blog.csdn.net/qq_64428099/article/details/126048709