数据结构-＞链表分类与oj（题），带你提升代码好感

✅作者���介：大家好，我是橘橙黄又青，一个想要与大家共同进步的男人

个人主页：橘橙黄又青-CSDN博客

1.链表的分类

前面我们学过顺序表，顺序表问题：

• 1. 中间/头部的插入删除，时间复杂度为O(N)
• 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
• 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

  这些问题，链表给出了相应的答案。

  概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。

   比如说我们前面学习的单链表就是如此。

  单链表是单向不循环不带头链表

   

  实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

  • 1. 单向、双向
  • 2. 带头、不带头
  • 3. 循环、非循环

    又称2x2x2 

    图解：

     

    • 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    • 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。 

      2.链表相关基础oj

      题目	链接
      设计链表	. - 力扣（LeetCode）
      两数相加	. - 力扣（LeetCode）
      合并两个有序链表	. - 力扣（LeetCode）
      两两交换链表中的节点	. - 力扣（LeetCode）
      删除排序链表中的重复元素	. - 力扣（LeetCode）
      删除排序链表中的重复元素II	. - 力扣（LeetCode）
      相交链表	. - 力扣（LeetCode）
      移除链表元素	. - 力扣（LeetCode）
      回文链表	. - 力扣（LeetCode）
      奇偶链表	. - 力扣（LeetCode）
      链表的中间结点	. - 力扣（LeetCode）
      链表最大孪生和	. - 力扣（LeetCode）
      两两交换链表中的节点	404: This page could not be found

      合并两个链表中，可以安排一个哨兵（头）可以减少判断空的代码。

      哨兵位的申请：

      这些都是比较好的题目，

      接下来我们分析几道题目

      题目	链接
      反转链表	. - 力扣（LeetCode）
      反转链表II	. - 力扣（LeetCode）
      链表中间节点问题	. - 力扣（LeetCode）
      环形链表的约瑟夫问题	环形链表的约瑟夫问题_牛客题霸_牛客网

      2.1第一个反转链表

      第一种：头插法

      /** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */ //头插术typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) {    ListNode* returnHead = NULL;    ListNode* ListLt = head;    while(ListLt != NULL){        //保存下一个节点        ListNode* temp = ListLt -> next;        //换头手术        ListLt -> next = returnHead;        returnHead = ListLt;        //迭代        ListLt = temp;    }    return returnHead;}

      这里说一个错误代码：

      输出结果为1，为什么来：

       

      所以temp要保存下一个节点。 

      第二种解法：

      三指针法：

      代码：

      /** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) {    if(head == NULL){        return head;    }    ListNode* n1 = NULL;    ListNode* n2 = head;    ListNode* n3 = head -> next;    ListNode* pcur = head;    while(n2){        n2-> next = n1;        n1 = n2;        n2 = n3;        if(n3){//这里防止n3为空，如果为空就无next            n3 = n3 -> next;         }    }    return n1;}

      图解：

      链表II与这个差不多，思路更为复杂。 

      2.2链表中间节点问题

      可以遍历链表计数除2，也可以使用双指针法

      双指针法：

      思路：

      代码：

      /** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */ typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) {    ListNode* slow,*fast;    slow = fast = head;    while(fast && fast -> next){        slow = slow -> next;        fast = fast -> next -> next;    }    return slow;}

      值得注意的是循环条件不能写成 fast -> next &&fast ，原因是计算机编译器是从左往右编译的，如果fast为空，就没有fast -> next。

      快慢指针法以后会经常使用务必理解.

      2.3.环形链表的约瑟夫问题 

      题目:

      这里我们输入Li 它就有暗示，说明已经有结构体结构了

      解题代码：

      /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * *  * @param n int整型  * @param m int整型  * @return int整型 */ typedef struct ListNode ListNode;//申请一个节点 ListNode* BuyNode(int x){    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));    newNode -> val = x;    newNode -> next = NULL;    return newNode; } ListNode* creteList(int n){    ListNode* phead = BuyNode(1);    ListNode* ptail = phead;    //创建链表和标号    for (int i = 2; i  next = BuyNode(i);        ptail = ptail -> next;    }    //链表首尾链接    ptail -> next = phead;    return phead; }#include int ysf(int n, int m ) {    //逢m删除节点    ListNode* head = creteList(n);    ListNode* pcur = head;    //前驱节点    ListNode* prev = NULL;        int conut = 1;    while (pcur ->next != pcur) {        if(conut == m){            //删除当前节点            prev -> next = pcur ->next;            free(pcur);            //删除节点后往后走，让pcur走到新的位置，conut为初始值            pcur = prev -> next;            conut = 1;        }        else{            //pcur往后走            prev = pcur;            pcur =  pcur -> next;            conut++;        }    }    //此时pcur节点就是活下来的节点    return pcur -> val;}

      试试效果：

       

      3.上节链表代码建议重复观看

      SList.c文件：

       SList.h文件

       test.c文件测试代码： 

       test.c文件代码

      #include"SList.h"//void SlistTest01() {// //链表的打印//SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));//node1->data = 1;//SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));//node2->data = 2;//SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));//node3->data = 3;//SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));//node4->data = 4;////node1->next = node2;//node2->next = node3;//node3->next = node4;//node4->next = NULL;////SLTNode* plist = node1;//SLTPrint(plist);//}void SlistTest02() {//尾插测试SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist); //1->2->3->4->NULL//头插测试//SLTPushFront(&plist, 5);//SLTPrint(plist);          //5->1->2->3->4->NULL//SLTPushFront(&plist, 6);//SLTPrint(plist);         //6->5->1->2->3->4->NULL//SLTPushFront(&plist, 7);//SLTPrint(plist);         //7-6->5->1->2->3->4->NULLSLTPopBack(&plist);SLTPrint(plist);//1->2->3->NULLSLTPopBack(&plist);SLTPrint(plist);//1->2->3->NULLSLTPopBack(&plist);SLTPrint(plist);//1->2->3->NULLSLTPopBack(&plist);SLTPrint(plist);//1->2->3->NULLSLTPopBack(&plist);SLTPrint(plist);//1->2->3->NULL}void SlistTest03() {SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist); //1->2->3->4->NULLSListDesTroy(&plist);头删//SLTPopFront(&plist);//SLTPrint(plist);    //2->3->4->NULL//SLTPopFront(&plist);//SLTPrint(plist);    //3->4->NULL//SLTPopFront(&plist);//SLTPrint(plist);    //4->NULL//SLTPopFront(&plist);//SLTPrint(plist);    //NULL//SLTPopFront(&plist);//SLTPrint(plist);    //assert//查找测试//SLTNode* FindRet = SLTFind(&plist, 3);//if (FindRet) {//printf("找到了！\n");//}//else {//printf("未找到！\n");//}//SLTInsert(&plist, FindRet, 100);//SLTInsertAfter(FindRet, 100);//删除指定位置的节点测试//SLTErase(&plist, FindRet);//SLTPrint(plist); //1->2->3->NULL}int main() {//SlistTest01();//SlistTest02();SlistTest03();return 0;}

      SList.c文件代码：

      #include"SList.h"//打印void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}//开辟空间SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;}//void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//开辟空间SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;}//头插void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;}//尾删void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点，有多个节点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;}//头删void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}//查找SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur) //等价于pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;}//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头结点if (pos == *pphead) {//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;}//在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;}//删除pos节点void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos) {//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}//删除pos之后的节点void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能为空assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}//销毁链表void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;}

      SList.h文件代码：

      #pragma once#include#include#includetypedef int SLTDataType;//链表是由节点组成typedef struct SListNode{SLTDataType data;struct SListNode* next;}SLTNode;//typedef struct SListNode SLTNode;//打印链表void SLTPrint(SLTNode* phead);//链表的头插、尾插void SLTPushBack(SLTNode** pphead, SLTDataType x);void SLTPushFront(SLTNode** pphead, SLTDataType x);//链表的头删、尾删void SLTPopBack(SLTNode** pphead);void SLTPopFront(SLTNode** pphead);//查找SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点void SLTEraseAfter(SLTNode* pos);//销毁链表void SListDesT

      今天就到这里了，都看到这里了，点一个赞吧，感谢观看。