devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】链表总结_链表数据结构

作者：Li_阴宅 | 2024-07-13 23:54:07

赞

踩

链表数据结构

一、链表

    • 链表的引入：

在使用顺序表的过程中，我们能感受到顺序表有以下几个缺点

1）空间不够，需要扩容。扩容（异地）是有一定代价的，其次还可能存在一定的空间浪费。

2）头部或者中部的插入删除，需要挪动数据，效率低下。

面对以上几个问题，我们引入链表结构来解决。

    • 链表的概念及结构：

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表

中的指针链接次序实现的 。

链表的逻辑结构：

链表的现实结构：

注意：

  • 从图中我们可以看出，链表在逻辑结构中是连续的，但在物理结构上链表不一定连续。

  • 链表的结点一般是从堆中申请，而申请的空间不一定连续。

    • 链表的分类：

链表的结构非常繁多，但实际应用中我们只能用到两类链表：

单向不带头不循环链表：

双向带头循环链表：

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

    • 链表的实现：

  • 单向不带头不循环链表：

4.1单链表结构创建及功能

  1. typedef int SLDataType;
  2. //单链表
  3. typedef struct SListNode
  4. {
  5.     SLDataType data;
  6.     struct SListNode* next;
  7. }SLTNode;
  8.  
  9. //创建节点
  10. SLTNode* BuySLTNode(SLDataType x);
  11. //向链表中填入数据
  12. SLTNode* CreateSList(int n);
  13. //打印链表
  14. void SLTPrint(SLTNode* phead);
  15. //尾插尾删
  16. void SLTPushBack(SLTNode** pphead, SLDataType x);
  17. void SLTPopBack(SLTNode** pphead);
  18. //头插头删
  19. void SLTPushFront(SLTNode** pphead,SLDataType x);
  20. void SLTPopFront(SLTNode* pphead);
  21. //查找节点
  22. SLTNode* SLTFind(SLTNode* phead, SLDataType x);
  23. //单链表在pos位置后插入数据
  24. void SLTInsertAfter(SLTNode* pos, SLDataType x);
  25. //单链表删除pos后一位的数据
  26. void SLTEraseAfter(SLTNode* pos);
  27. //单链表在pos之前插入数据
  28. void SLTInsert(SLTNode** pphead,SLTNode* pos,SLDataType x);
  29. //单链表删除pos位置的数据
  30. void SLTErase(SLTNode** pphead,SLTNode* pos);
  31. //释放单链表空间
  32. void SLTDestroy(SLTNode** pphead);
在实现功能前，我们需要弄懂为什么有的函数传的参数不一样？

  • 仔细观察，在一些函数中传二级指针，都有一个改头结点的操作，那为什么改头结点需要使用二级指针？

引例：

  1.   void Swap1(int* p1, int* p2)
  2. {
  3.     int tmp = *p1;
  4.     *p1 = *p2;
  5.     *p2 = tmp;
  6. }
  7. void Swap2(int** pp1, int** pp2)
  8. {
  9.     int* tmp = *pp1;
  10.     *pp1 = *pp2;
  11.     *pp2 = tmp;
  12. }
  13. void Test()
  14. {
  15.     int a = 0, b = 1;
  16.     int* ptr1 = &a, * ptr2 = &b;
  17.     //交换a与b
  18.     //即a原本为0，b为1，交换后a为1，b为0
  19.     Swap1(&a, &b);
  20.     //交换ptr1与ptr2
  21.     //即ptr1原本指向a，ptr2指向b，交换后ptr1指向b，ptr2指向a
  22.     Swap2(&ptr1, &ptr2);
  23. }

众所周知，在函数中，对于形参的修改不会影响到实参，会导致函数不会起到预期的作用，因此对于修改实参，我们采用指针的方法。

同理，头结点的类型是SLTNode*，如果我们使用SLTNode*类型的指针修改头结点的指向，形参的改变不会影响实参，头结点的指向不会发生改变，而对于SLTNode*类型的修改，我们采用二级指针来修改它的指向，因此传的参数为SLTNode**类型。

4.2单链表的功能实现：

  1. //创建节点
  2. SLTNode* BuySLTNode(SLDataType x)
  3. {
  4.     SLTNode* newnode = malloc(sizeof(SLTNode));
  5.     if (newnode == NULL)
  6.     {
  7.         perror("malloc fail");
  8.         exit(-1);
  9.     }
  10.     newnode->data = x;
  11.     newnode->next = NULL;
  12.     return newnode;
  13. }
  14.  
  15. //创建链表（将节点链接成链表）
  16. SLTNode* CreateSList(int n)
  17. {
  18.     //phead用于找到头节点  ptail用于链接节点
  19.     SLTNode* phead = NULL, *ptail = NULL;
  20.     int x = 0;
  21.     for (int i = 0; i < n; i++)
  22.     {
  23.         //scanf("%d", &x);
  24.         //SLTNode* newnode = BuySLTNode(x);//创建节点
  25.         SLTNode* newnode = BuySLTNode(i);
  26.         if (phead == NULL)
  27.         {
  28.             ptail = phead = newnode;
  29.         }
  30.         else
  31.         {
  32.             ptail->next = newnode;//链接新的节点
  33.             ptail = newnode;//让ptail成为下一个节点
  34.         }
  35.     }
  36.     return phead;
  37. }
  38.  
  39. //打印链表
  40. void SLTPrint(SLTNode* phead)
  41. {
  42.     SLTNode* cur = phead;
  43.     while (cur != NULL)
  44.     {
  45.         printf("%d->", cur->data);
  46.         //打印整个节点
  47.         /*printf("[%d|%p]->", cur->data, cur->next);*/
  48.         cur = cur->next;//将下一个节点的地址赋值给cur
  49.     }
  50.     printf("NULL\n");
  51. }
  52.  
  53. //尾插
  54. void SLTPushBack(SLTNode** pphead, SLDataType x)
  55. {
  56.     
  57.     SLTNode* newnode = BuySLTNode(x);
  58.     if (*pphead == NULL)
  59.     {
  60.         //将Plist指向newnode，即将空表的表头链接节点
  61.         *pphead = newnode;
  62.     }
  63.     else
  64.     {
  65.         SLTNode* tail = *pphead;
  66.         //找尾
  67.         while (tail->next)
  68.         {
  69.             tail = tail->next;
  70.         }
  71.         //链接
  72.         tail->next = newnode;
  73.     }
  74. }
  75.  
  76. //尾删
  77. void SLTPopBack(SLTNode** pphead)
  78. {
  79.     assert(*pphead);//表不能为空
  80.  
  81.     if ((*pphead)->next == NULL)//表中只剩一个节点
  82.     {
  83.         free(*pphead);
  84.         *pphead = NULL;
  85.     }
  86.     else
  87.     {
  88.         //方法一：
  89.         //SLTNode* tail = *pphead;
  90.         //SLTNode* prev = NULL;//找到尾删的前一项
  91.         找尾
  92.         //while (tail->next)
  93.         //{
  94.         //    prev = tail;
  95.         //    tail = tail->next;
  96.         //}
  97.         //free(tail);
  98.         //prev->next = NULL;
  99.  
  100.         //方法二：
  101.         SLTNode* tail = *pphead;
  102.         //找尾
  103.         while (tail->next->next)
  104.         {
  105.             tail = tail->next;
  106.         }
  107.         free(tail->next);
  108.         tail->next = NULL;
  109.     }
  110.  
  111. }
  112.  
  113. //头插
  114. void SLTPushFront(SLTNode** pphead, SLDataType x)
  115. {
  116.     SLTNode* newnode = BuySLTNode(x);
  117.     newnode->next = *pphead;//将节点与单链表链接
  118.     *pphead = newnode;//让新节点成为头节点
  119. }
  120.  
  121. //头删
  122. void SLTPopFront(SLTNode** pphead)
  123. {
  124.     assert(*pphead);
  125.     SLTNode* next = (*pphead)->next;//找到表中第二个节点
  126.     free(*pphead);//释放删除节点的空间
  127.     *pphead = next;//让第二个节点成为头节点
  128. }
  129.  
  130. //查找节点
  131. SLTNode* SLTFind(SLTNode* phead, SLDataType x)
  132. {
  133.     SLTNode* cur = phead;
  134.     while (cur)
  135.     {
  136.         if ((cur->data) == x)
  137.         {
  138.             return cur;
  139.         }
  140.         cur = cur->next;
  141.     }
  142.     return NULL;
  143. }
  144.  
  145. //单链表在pos位置后插入数据
  146. void SLTInsertAfter(SLTNode* pos, SLDataType x)
  147. {
  148.     assert(pos);
  149.     SLTNode* newnode = BuySLTNode(x);
  150.     newnode->next = pos->next;//先将pos的后一位链接到新节点
  151.     pos->next = newnode;//将新节点链接到pos上
  152. }
  153.  
  154. //单链表删除pos后一位的数据
  155. void SLTEraseAfter(SLTNode* pos)
  156. {
  157.     assert(pos);
  158.     if (pos->next == NULL)
  159.     {
  160.         return;
  161.     }
  162.     else
  163.     {
  164.         SLTNode* prev = pos->next;//保存pos后一位的地址
  165.         pos->next = prev->next;//将pos与prev的下一个节点链接
  166.         free(prev);//释放pos后一位节点空间
  167.     }
  168. }
  169.  
  170. //单链表在pos之前插入数据
  171. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
  172. {
  173.     assert(pos);
  174.     if (*pphead == pos)//当pos为表头就是头插
  175.     {
  176.         SLTPushFront(pphead, x);
  177.     }
  178.     else
  179.     {
  180.         SLTNode* prev = *pphead;//保存pos前一节点的地址
  181.         while (prev->next != pos)//寻找pos前一节点
  182.         {
  183.             prev = prev->next;
  184.         }
  185.         SLTNode* newnode = BuySLTNode(x);
  186.         newnode->next = pos;//链接节点-后
  187.         prev->next = newnode;//链接节点-前
  188.     }
  189. }
  190.  
  191. //单链表删除pos位置的数据
  192. void SLTErase(SLTNode** pphead, SLTNode* pos)
  193. {
  194.     assert(pos);
  195.     assert(*pphead);
  196.     if (*pphead == pos)//当pos为表头就是头删
  197.     {
  198.         SLTPopFront(pphead);
  199.     }
  200.     else
  201.     {
  202.         SLTNode* prev = *pphead;//保存pos前一节点
  203.         while (prev->next != pos)//寻找pos前一节点
  204.         {
  205.             prev = prev->next;
  206.         }
  207.         prev->next = pos->next;//删除pos节点，链接前后节点
  208.         free(pos);//释放pos节点空间
  209.     }
  210. }
  211.  
  212. //释放单链表空间
  213. void SLTDestroy(SLTNode** pphead)
  214. {
  215.     SLTNode* cur = *pphead; //替身指针 （释放节点）
  216.     while (cur)
  217.     {
  218.         SLTNode* next = cur->next; //保存释放空间的下一个节点地址
  219.         free(cur);//释放链表节点
  220.         cur = next;//释放下一个节点
  221.     }
  222.     *pphead = NULL;//将链表表头指针置为NULL，防止再次错误调用。（野指针）
  223. }
相比于顺序表，单链表有优点，相对的这种数据结构也有缺点

  • 优点：头插头删，时间复杂度为O(1)。

  • 缺点：当我们想要在任意位置插入删除数据，需要记录他的前一个节点，这就需要去寻找这个节点，需要遍历一遍整个链表，因此时间复杂度为O(N)。

既然单链表这种数据结构有这种缺陷，那是否有4方法来解决这个缺点？

对此我们引入带头双向循环链表这种数据结构来解决整个问题。

4.3循环链表结构创建及功能：

  1. typedef int DLDataType;
  2. typedef struct ListNode
  3. {
  4.     struct ListNode* next;
  5.     struct ListNode* prev;
  6.     DLDataType data;
  7. }DLTNode;
  8. //创建节点
  9. DLTNode* BuyNode(DLDataType x);
  10. //初始化头节点
  11. DLTNode* DListInit();
  12. //打印聊表：
  13. void DListPrint(DLTNode* pHead);
  14. //尾插尾删
  15. void DListPushBack(DLTNode* pHead,DLDataType X);
  16. void DListPopBack(DLTNode* pHead);
  17. //头插头删
  18. void DListPushFront(DLTNode* pHead,DLDataType x);
  19. void DListPopFront(DLTNode* pHead);
  20. //查找
  21. DLTNode* DLFind(DLTNode* pHead,DLDataType x);
  22. //任意位置插入删除
  23. void DLInsert(DLTNode* pos, DLDataType* x);//pos前
  24. void DLErase(DLTNode* pos);
  25. //判断链表为空
  26. bool DLEmpty(DLTNode* pHead);
  27. //链表数据个数
  28. size_t DLSize(DLTNode* pHead);
  29. //销毁链表
  30. void DLDestroy(DLTNode* pHead);
为什么在这个链表中，函数的参数没有使用二级指针？

在实现这个链表时，我们使用哨兵位的头结点，因此在链接或删除结点时，仅仅改变结点中的next或者prev指针，实际上就是改变结构体，使用结构体指针就可以，不需要使用二级指针。

4.4循环链表的功能实现：

  1. //创建节点
  2. DLTNode* BuyNode(DLDataType x)
  3. {
  4.     DLTNode* newnode = (DLTNode*)malloc(sizeof(DLTNode));
  5.     if (newnode == NULL)
  6.     {
  7.         perror("malloc fail");
  8.         exit(-1);
  9.     }
  10.     newnode->next = NULL;
  11.     newnode->prev = NULL;
  12.     newnode->data = x;
  13.     return newnode;
  14. }
  15. //初始化头节点
  16. DLTNode* DListInit()
  17. {
  18.     DLTNode* pHead = BuyNode(-1);
  19.     pHead->next = pHead;
  20.     pHead->prev = pHead;
  21.  
  22.     return pHead;
  23. }
  24. //打印链表
  25. void DListPrint(DLTNode* pHead)
  26. {
  27.     assert(pHead);
  28.     DLTNode* cur = pHead->next;
  29.     while (cur != pHead)
  30.     {
  31.         printf("-%d", cur->data);
  32.         cur = cur->next;
  33.     }
  34.     printf("\n");
  35. }
  36. //尾插尾删
  37. void DListPushBack(DLTNode* pHead, DLDataType x)
  38. {
  39.     assert(pHead);
  40.     //DLTNode* newnode = BuyNode(x);
  41.     //DLTNode* tail = pHead->prev;//找到尾节点
  42.  
  43.     //tail->next = newnode;//与前一节点双向链接
  44.     //newnode->prev = tail;
  45.  
  46.     //newnode->next = pHead;//与头节点双向链接
  47.     //pHead->prev = newnode;
  48.     DLInsert(pHead, x);
  49. }
  50. void DListPopBack(DLTNode* pHead)
  51. {
  52.     assert(pHead);
  53.     assert(pHead->next != pHead);
  54.     //DLTNode* tail = pHead->prev;//找到尾节点
  55.     //DLTNode* tailprev = tail->prev;//找到尾节点的前节点
  56.     //pHead->prev = tailprev;//将前节点与头节点双向链接
  57.     //tailprev->next = pHead;
  58.     //free(tail);
  59.     DLErase(pHead->prev);
  60. }
  61. //头插头删
  62. void DListPushFront(DLTNode* pHead, DLDataType x)
  63. {
  64.       assert(pHead);
  65.     //DLTNode* newnode = BuyNode(x);
  66.     //DLTNode* tail = pHead->next;//找到头节点下一位
  67.     //newnode->next = tail;//将插入节点与tail相连
  68.     //tail->prev = newnode;
  69.  
  70.     //newnode->prev = pHead;//将插入节点与头节点相连
  71.     //pHead->next = newnode;
  72.     DLInsert(pHead->next, x);
  73. }
  74. void DListPopFront(DLTNode* pHead)
  75. {
  76.     assert(pHead);
  77.     assert(pHead->next != pHead);
  78.     //DLTNode* cur = pHead->next;//找到删除节点
  79.     //DLTNode* next = cur->next;//找到删除节点的下一位
  80.  
  81.     //pHead->next = next;//链接头节点与下一位节点
  82.     //next->prev = pHead;
  83.     //free(cur);
  84.     DLErase(pHead->next);
  85. }
  86. //查找
  87. DLTNode* DLFind(DLTNode* pHead,DLDataType x)
  88. {
  89.     assert(pHead);
  90.     DLTNode* cur = pHead->next;
  91.     while(cur != pHead)
  92.     {
  93.         if (cur->data == x)
  94.         {
  95.             return cur;
  96.         }
  97.         cur = cur->next;
  98.     }
  99.     return NULL;
  100. }
  101. //任意位置插入删除
  102. void DLInsert(DLTNode* pos, DLDataType* x)
  103. {
  104.     assert(pos);
  105.     DLTNode* newnode = BuyNode(x);
  106.     DLTNode* posprev = pos->prev;//pos的前一节点
  107.     //链接三个节点  posprev newnode pos
  108.     posprev->next = newnode;//新节点与前节点链接
  109.     newnode->prev = posprev;
  110.  
  111.     newnode->next = pos;//新节点与pos位置链接
  112.     pos->prev = newnode;
  113. }
  114. void DLErase(DLTNode* pos)
  115. {
  116.     assert(pos);
  117.     DLTNode* posprev = pos->prev;//找到前一个节点
  118.     DLTNode* posnext = pos->next;//找到后一个节点
  119.     //链接 posprev  posnext
  120.     posprev->next = posnext;
  121.     posnext->prev = posprev;
  122.     free(pos);
  123. }
  124. //判断链表为空
  125. bool DLEmpty(DLTNode* pHead)
  126. {
  127.     assert(pHead);
  128.     /*if (pHead->next == pHead)
  129.     {
  130.         return true;
  131.     }
  132.     else
  133.         return false;*/
  134.     return pHead->next == pHead;
  135. }
  136. //链表数据个数
  137. size_t DLSize(DLTNode* pHead)
  138. {
  139.     assert(pHead);
  140.     size_t sum = 0;
  141.     DLTNode* cur = pHead->next;
  142.     while (cur != pHead)
  143.     {
  144.         sum++;
  145.         cur = cur->next;
  146.     }
  147.     return sum;
  148. }
  149. //销毁链表
  150. void DLDestroy(DLTNode* pHead)
  151. {
  152.     assert(pHead);
  153.     DLTNode* cur = pHead->next;
  154.     while (cur != pHead)
  155.     {
  156.         DLTNode* next = cur->next;
  157.         free(cur);
  158.         cur = next;
  159.     }
  160.     free(pHead);
  161. }

二、链表的OJ

    • 删除链表中等于给定值 val 的所有节点

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：创建一个新的头结点，遍历源链表，将不等于val的节点链接到创建的新节点后

代码实现：

  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2. {    
  3.     struct ListNode* rhead, *tail;
  4.     tail = rhead = (struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
  5.     tail->next = NULL;
  6.     struct ListNode* cur = head;
  7.     while(cur)
  8.     {
  9.         struct ListNode* next = cur->next;//记录下一节点
  10.         if(cur->val != val)
  11.         {
  12.             tail->next = cur;//链接到新节点
  13.             cur->next = NULL;//将已链接的节点与原链表断开
  14.             tail = tail->next;
  15.         }
  16.         cur = next;
  17.     }
  18.     return rhead->next;
  19. }

    • 反转一个链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路1：遍历原链表，将数据头插到新链表 
  1. struct ListNode* reverseList(struct ListNode* head)
  2. {
  3.    struct ListNode* cur = head;
  4.    struct ListNode* rhead = NULL;
  5.    while(cur)
  6.    {
  7.        struct ListNode* next = cur->next;//保留下一个节点
  8.        //头插
  9.        cur->next = rhead;
  10.        rhead = cur;
  11.        cur = next;
  12.    }
  13.    return rhead;
  14. }
思路2：三指针迭代，将链表反转 

  1. struct ListNode* reverseList(struct ListNode* head) {
  2.     if (head == NULL || head->next == NULL)//链表为空，或者就一个元素
  3.         return head;
  4.     struct ListNode* prev = NULL, * cur = head, * next = head->next;
  5.     while (cur)
  6.     {
  7.         //反转链表
  8.         cur->next = prev;
  9.         //迭代
  10.         prev = cur;
  11.         cur = next;
  12.         if (next)
  13.             next = next->next;
  14.     }
  15.     return prev;
  16. }

3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

思路：设置快慢指针，快指针一次走两部，慢指针走一步，奇数个和偶数个时情况不同。 
  1. struct ListNode* middleNode(struct ListNode* head)
  2. {
  3.         struct ListNode* fast, *slow;
  4.         fast = slow = head;
  5.         while(fast && fast->next)
  6.         {
  7.             slow = slow->next;
  8.             fast = fast->next->next;
  9.         }
  10.         return slow;
  11. }

4.输入一个链表，输出该链表中倒数第k个结点

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

思路：设置快慢指针，通过观察，让快指针先走k步，然后快指针和慢指针同时走，当快指针为空时，慢指针所在位置即为倒数第k位。 
  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
  2. {
  3.           struct ListNode* fast,*slow;
  4.           fast = slow = pListHead;
  5.           while(k--)
  6.           {
  7.             //链表没有k步
  8.             if(fast == NULL)
  9.             {
  10.                 return NULL;
  11.             }
  12.             fast = fast->next;
  13.           }
  14.           
  15.           while(fast)
  16.           {
  17.             slow = slow->next;
  18.             fast = fast->next;
  19.           }
  20.           return slow;
  21. }

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：新建一个头结点，遍历两条链表，并比较其val大小，小的链接到新链表中。 
  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  2. {
  3.       struct ListNode* guard,*tail;
  4.       guard = tail =  (struct ListNode*)malloc(sizeof(struct ListNode));
  5.       guard ->next = NULL;
  6.       while(list1 && list2)
  7.       {
  8.           if(list1->val < list2->val)
  9.           {
  10.               tail->next = list1;
  11.               tail = tail->next;
  12.               list1 = list1->next;
  13.           }
  14.           else
  15.           {
  16.               tail->next = list2;
  17.               tail = tail->next;
  18.               list2 = list2->next;
  19.           }
  20.       } 
  21.       if(list1)//第一条剩余
  22.       {
  23.           tail->next = list1;
  24.       }
  25.       if(list2)//第二条剩余
  26.       {
  27.           tail->next = list2;
  28.       }
  29.       struct Node* head = guard->next;//返回哨兵的下一位才是链表
  30.       free(guard);
  31.  
  32.       return head;
  33. }

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：新创建两个链表，一个用来链接小于x的，另一个用来链接大于x的，然后将两条链表链接，将合并的链表链接到原链表头节点。 
  1. class Partition {
  2. public:
  3.    ListNode* partition(ListNode* pHead, int x) {
  4.     struct ListNode* cur = pHead;
  5.     struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
  6.     lessTail = lessHead = (ListNode*)malloc(sizeof(ListNode));
  7.     greaterTail = greaterHead = (ListNode*)malloc(sizeof(ListNode));
  8.     lessTail->next = NULL;
  9.     greaterTail->next = NULL;
  10.     while(cur)
  11.     {
  12.         if(cur->val<x)
  13.         {
  14.             lessTail->next = cur;
  15.             lessTail = lessTail->next;
  16.         }
  17.         else 
  18.         {
  19.             greaterTail->next = cur;
  20.             greaterTail = greaterTail->next;
  21.         }
  22.         cur = cur->next;
  23.     }
  24.     lessTail->next = greaterHead->next;
  25.     greaterTail->next = NULL;
  26.     pHead = lessHead->next;
  27.     free(lessHead);
  28.     free(greaterHead);
  29.     return pHead;
  30.     }
  31. };

7.链表的回文结构

OR36 链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：先找到链表的中间位置的节点，然后将中间节点以后的节点逆置，创建一个新节点，然后将逆置后的链表链接到新节点后，比较原链表与新链表，若前半段相同，则为回文。 
  1. class PalindromeList {
  2.   public:
  3.     struct ListNode* middleNode(struct ListNode* head) {
  4.         struct ListNode* fast, *slow;
  5.         fast = slow = head;
  6.         while (fast && fast->next) {
  7.             slow = slow->next;
  8.             fast = fast->next->next;
  9.         }
  10.         return slow;
  11.     }//找中间功能
  12.  
  13.     struct ListNode* reverseList(struct ListNode* head) {
  14.         struct ListNode* cur = head;
  15.         struct ListNode* rhead = NULL;
  16.         while (cur) {
  17.             struct ListNode* next = cur->next;//保留下一个节点
  18.             //头插
  19.             cur->next = rhead;
  20.             rhead = cur;
  21.             cur = next;
  22.         }
  23.         return rhead;
  24.     }//逆置功能
  25.  
  26.     bool chkPalindrome(ListNode* A) {
  27.         // write code here
  28.         struct ListNode* mid = middleNode(A);
  29.         struct ListNode* rhead = reverseList(mid);
  30.         while(A && rhead)
  31.         {
  32.             if(A->val != rhead->val)
  33.             {
  34.                 return false;
  35.             }
  36.             A = A->next;
  37.             rhead = rhead->next;
  38.         }
  39.     return true; 
  40.     }
  41. };

8.输入两个链表，找出它们的第一个公共结点。

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路：首先判断两条链表是否相交，即判断链表的最后一个节点地址是否相同，求出两条链表的长度，设置两个指针用来遍历链表，求出长度的差值，让长的链表的指针先走差值的步数，然后两个指针同时走，俩指针相等，即为交点。 
  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  2. {
  3.     struct ListNode* curA = headA;
  4.     struct ListNode* curB = headB;
  5.     int lenA = 0, lenB = 0;
  6.     //求得A、B链的长度
  7.     while(curA->next)
  8.     {
  9.         lenA++;
  10.         curA = curA ->next;
  11.     }
  12.     while(curB->next)
  13.     {
  14.         lenB++;
  15.         curB = curB->next;
  16.     }
  17.     //判断是否相交 （链尾相同）
  18.     if(curA != curB)
  19.     {
  20.         return NULL;
  21.     }
  22.     //求出两链表个数差值
  23.     int gap = abs(lenA-lenB);
  24.     //区分长短链
  25.     struct ListNode* longlist = headA, *shortlist = headB;
  26.     if(lenA < lenB)
  27.     {
  28.         shortlist = headA;
  29.         longlist = headB;
  30.     }
  31.     //长链先遍历差距步
  32.     while(gap--)
  33.     {
  34.         longlist = longlist->next;
  35.     }
  36.     //同时遍历
  37.     while(longlist != shortlist)
  38.     {
  39.         longlist = longlist->next;
  40.         shortlist = shortlist->next;
  41.     }
  42.     return longlist;
  43. }

9.给定一个链表，判断链表中是否有环

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：设置快慢，快指针一次走两步，慢指针一次走一步，当慢指针入环时，问题转化为快指针追赶慢指针，根据相对运动，两个指针每走一次，相对距离就会减小一，快指针就会离慢指针更近一步，最终二者在环中相遇，即为环，如果不是环，快指针一定先走到末端。 
  1. bool hasCycle(struct ListNode *head) 
  2. {
  3.  
  4.     struct ListNode* fast = head, *slow = head;
  5.     while(fast && fast->next)
  6.     {
  7.  
  8.         fast = fast->next->next;
  9.         slow = slow->next;
  10.         if(fast == slow)
  11.          {
  12.             return true;
  13.          }
  14.     }
  15.     return false;
  16. }

扩展问题：

  • 为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

  • 快指针一次走3步，走4步，...n步行吗？

不一定，假设快指针一次走3步，慢指针在入环后，快指针以相对2个单位追赶慢指针，如果N为奇数，N为俩指针之间的距离，则他俩之间的距离变化为：N-2,N-4,.........3,1,-1.当变为-1时，则又开始新一轮的追击，而他俩之间的距离为C-1，C为整个环的周长，如果C-1为偶数，则可以追赶上，若为奇数，则追不上。

由以上可知，只要fast与slow的相对速度为1，无论如何都可以追上。

10.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

思路：

我们观察可以看出，这一类问题可总结出规律：

假设进环前长度为L，环的周长为C，进环点与相遇点的距离为N

公式推导：

  • fast走的距离 = 2*slow走的距离

  • slow走的距离 = L+N

  • fast走的距离 = L+n*C+N（slow进环前，fast已经走了n圈）

为什么slow走的不是L+n*C+X呢? 即为什么slow在圈里一定走了不到一圈就相遇了呢？我们知道当slow刚刚进圈时slow与fast之间的距离一定小于C-1,fast一次走两步，slow一次走一步，距离逐渐减小，即一定走了小于C-1次就会相遇，因此推出此时slow走了不到一圈。

则 2*(L+N) = L+n*C+N,即L = n*C-N

得到：

  • 由此可以，一个指针在头结点，一个指针在相遇点，两指针同时走，一定可以相遇，相遇点即为进环点。

  • 同时问题也可以转化成相交问题，我们可以创建一个指针记录相遇点meet的后一位节点，然后令其与相遇点断开，那么问题就变成了链链表的相交问题。

公式法：

  1. struct ListNode *detectCycle(struct ListNode *head) {
  2.     struct ListNode* fast = head, *slow = head;
  3.     while(fast && fast->next)
  4.     {
  5.  
  6.         fast = fast->next->next;
  7.         slow = slow->next;
  8.         if(fast == slow)
  9.          {
  10.             struct ListNode* meet = slow;
  11.             while(head != meet)
  12.             {
  13.                 head = head->next;
  14.                 meet = meet->next;
  15.             }
  16.             return meet;
  17.          }
  18.     }
  19.     return NULL;
  20. }

相交法：

  1. struct ListNode* hasCycle(struct ListNode *head) 
  2. {
  3.  
  4.     struct ListNode* fast = head, *slow = head;
  5.     while(fast && fast->next)
  6.     {
  7.  
  8.         fast = fast->next->next;
  9.         slow = slow->next;
  10.         if(fast == slow)
  11.          {
  12.             return slow;
  13.          }
  14.     }
  15.     return NULL;
  16. }
  17.  
  18. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  19. {
  20.     struct ListNode* curA = headA;
  21.     struct ListNode* curB = headB;
  22.     int lenA = 0, lenB = 0;
  23.     //求得A、B链的长度
  24.     while(curA->next)
  25.     {
  26.         lenA++;
  27.         curA = curA ->next;
  28.     }
  29.     while(curB->next)
  30.     {
  31.         lenB++;
  32.         curB = curB->next;
  33.     }
  34.     //判断是否相交 （链尾相同）
  35.     if(curA != curB)
  36.     {
  37.         return NULL;
  38.     }
  39.     //求出两链表个数差值
  40.     int gap = abs(lenA-lenB);
  41.     //区分长短链
  42.     struct ListNode* longlist = headA, *shortlist = headB;
  43.     if(lenA < lenB)
  44.     {
  45.         shortlist = headA;
  46.         longlist = headB;
  47.     }
  48.     //长链先遍历差距步
  49.     while(gap--)
  50.     {
  51.         longlist = longlist->next;
  52.     }
  53.     //同时遍历
  54.     while(longlist != shortlist)
  55.     {
  56.         longlist = longlist->next;
  57.         shortlist = shortlist->next;
  58.     }
  59.     return longlist;
  60. }
  61. struct ListNode *detectCycle(struct ListNode *head) {
  62.  
  63.     struct ListNode* meet = hasCycle(head);
  64.     if(meet== NULL)
  65.     {
  66.         return NULL;
  67.     }
  68.     struct ListNode* rhead = meet->next;//记录相遇点的下一节点
  69.     meet->next = NULL;//断开环，防止进入死循环
  70.     struct ListNode* cur = head;
  71.     struct ListNode* meetagain = getIntersectionNode(cur,rhead);
  72.     meet->next = rhead;//恢复环
  73.     return meetagain;
  74. }

11.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中任何节点或空节点。要求返回这个链表的深度拷贝。

138. 复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。

random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

思路：

  • 方法一：

通过暴力的方法来查找random指针，通过i来记录random指针指向的节点位于整个链表的第几位，这种方法首先需要挨个遍历每个节点，找到节点random指针的指向，并用i来记录该节点是链表的第几个，从而当处理拷贝链表的过程中，再利用双层循环将每个特定的位置的random指向这个拷贝链表相对应的位置。

  • 方法二：

1.将链表的每一个节点拷贝出来，并链接到原节点的后一为

2.设置拷贝节点的random指针，拷贝节点的random指针指向的就是原节点的random指针指向的节点的后一节点（拷贝节点就在原节点后）。

3.将拷贝节点与原节点断开，并链接，恢复原链表。

  1. struct Node* copyRandomList(struct Node* head)
  2. {
  3.     //将链表每个节点拷贝并链接到本体后
  4.     struct Node* cur = head;
  5.     while(cur)
  6.     {
  7.         struct Node* next = cur->next;
  8.         struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
  9.         copy->val = cur->val;
  10.         //链接拷贝节点
  11.         cur->next = copy;
  12.         copy->next = next;
  13.  
  14.         cur = next;
  15.     }
  16.     //设置拷贝节点的random指针
  17.     cur = head;
  18.     while(cur)
  19.     {
  20.         struct Node* copy = cur->next;
  21.  
  22.         if(cur->random == NULL)
  23.         {
  24.             copy->random = NULL;
  25.         }   
  26.         else
  27.         {
  28.             copy->random = cur->random->next;
  29.         }
  30.  
  31.         cur = copy->next;
  32.     }
  33.     //将拷贝节点链接
  34.     cur = head;
  35.     struct Node* copyHead = NULL, *copyTail=NULL;
  36.     while(cur)
  37.     {
  38.         struct Node* copy = cur->next;
  39.         struct Node* next = copy->next;
  40.  
  41.         cur->next = next;
  42.         if(copyTail == NULL)
  43.         {
  44.             copyTail = copyHead = copy;
  45.         }
  46.         else
  47.         {
  48.             copyTail->next =copy;
  49.             copyTail = copyTail->next; 
  50.         }
  51.         cur = next;
  52.     }
  53.     return copyHead;
  54. }

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号