顿搜
飞过闲红千叶，夕岸在哪
类目归类
链表——算法设计 · 篇五
08/14
一、链表的构造和翻转
GitHub地址：链表的构造和翻转 .cpp
- ①、求单链表中节点的个数
1、可以采用依次查找的方法
2、也可以采用递归的方法求解链表的长度
- ②、反转单链表
1、如果单链表为空或者只有一个节点，无需翻转，直接返回头节点
2、设置三个指针，位置顺序依次为preverse，tmp，current，
3、将current赋值给tmp，current后移，tmp的next指向preverse，然后将tmp赋值给preverse
4、遍历完即可
## 二、链表中节点的查找和删除 > GitHub地址：链表中节点的查找和删除.cpp + ①、查找单链表中倒数第K个节点 > 1、设置前后两个指针，前面的指针先走到正向第K个节点 > 2、前后两个指针一起向前走，直到前面的指针指向最后一个节点 > 3、后面的指针所指向的节点就是倒数第K个节点 + ②、从尾到头打印链表 > 1、使用递归的方法 + ③、判断单链表中是否有环 > 1、设置快慢两个指针 > 2、快指针每次前进两步，慢指针每次前进一步 > 3、若快慢指针能够相遇，则说明有环 + ④、在O(1)时间复杂度内删除节点 > 1、将下一个节点的数据复制到本节点，然后删除下一个节点 > 2、若要删除的是最后一个节点，只能依次找到倒数第二个节点
## 三、带环的单链表中入环的第一个节点 > GitHub地址：带环的单链表中入环的第一个节点.cpp + ①、已知一个单链表中存在环，求进入环中的第一个节点 > 1、先判断是否存在环 > 2、如果存在环，快慢指针都以同样的速度前进，相遇即为第一个节点 ## 四、约瑟夫环 > GitHub地址：约瑟夫环.cpp > 1、双层循环，外层判断是否还有节点，内层循环遍历删除 ## 五、删除单链表中重复的元素 > GitHub地址：删除单链表中重复的元素（伪指针）.cpp + ①、删除重的元素 > 1、前后紧密相邻两个指针，判断两指针值是否一样，相同则改变指针指向下一个 > 2、可以引入伪指针，使得操作统一化 ## 六、单链表的 K 翻转 > GitHub地址：单链表的 K 翻转（伪指针）.cpp 先找到k个节点，再利用标题1下的第②条对其进行反转 ## 七、单链表中区间节点的翻转 > GitHub地址：单链表中区间节点的翻转.cpp。 先找到区间，再利用标题1下的第②条对其进行反转 ## 八、单链表节点的交叉重排 > GitHub地址：单链表节点的交叉重排.cpp + ①、重新排序链表，将一个链表拆分，然后重新组合 > 1、关键点在于链表个数是偶数还是奇数 > 2、根据链表的长度将链表分为两个部分，然后交叉连接即可 ## 九、单链表的分割 > GitHub地址：单链表的分割.cpp + ①、根据给定的值，将单链表分割成两部分 > 思路和第一章中，字符串排序的第①条相同 ## 十、单链表的合并 > GitHub地址：单链表的合并（非最小堆方法）.cpp + ①、合并K个已经排序好的链表 > 1、可以类似于合并几个已经排序好的数组这种思想，比如借助最小堆，每次将堆顶元素插入新的链表中 > 2、也可以使用数组来进行标记，每次从数组中挑选最小的节点直到所有链表的节点都被选中 ## 十一、单链表的排序 > GitHub地址：单链表的排序（归并）.cpp 对于链表的排序 使用归并排序最好
