文章目录
前言一、直观做法（一）线性表存储（二）链表中点+后半部分链表倒置+链表融合
二.代码（一）快慢指针法得链表中点（二）链表倒置（三）链表融合
总结
前言
C++中链表因为涉及指针的使用，所以一直是一大难题。本篇文章中将讲解如何使用快慢指针法得到链表中点，及链表的倒置操作。相信在本篇文章后你将了解这些用法。
传说门
提示：以下是本篇文章正文内容
一、直观做法
（一）线性表存储
转为线性表后，可以方便使用索引获得元素。但缺点是，空间复杂度会到达O(n)。另外，因为本文主要讲解链表操作，略过不提
（二）链表中点+后半部分链表倒置+链表融合
以样例为例。
输入
1 -> 2 -> 3 -> 4
链表中点
2
后半部分链表首节点：
3（链表中点的后一个节点）
后半部分链表倒置
4 -> 3
链表合并
1 -> 4 -> 3 -> 2
输入
1 -> 2 -> 3 -> 4 -> 5
链表中点
3
后半部分链表首节点：
4（链表中点的后一个节点）
后半部分链表倒置
5 -> 4
链表合并
1 -> 5 -> 2 -> 4 -> 3
二.代码
（一）快慢指针法得链表中点
ListNode
* findMid(ListNode
* head
){
ListNode
* slow
= head
;
ListNode
* fast
= head
;
while(fast
-> next
!= nullptr && fast
-> next
-> next
!= nullptr){
slow
= slow
-> next
;
fast
= fast
-> next
-> next
;
}
return slow
;
}
输入
1 -> 2 -> 3 -> 4
链表中点
2
（二）链表倒置
ListNode
* reverseList(ListNode
* head
){
ListNode
* prev
= nullptr;
ListNode
* cur
= head
;
while(cur
!= nullptr){
ListNode
* nextNode
= cur
-> next
;
cur
-> next
= prev
;
prev
= cur
;
cur
= nextNode
;
}
return prev
;
}
倒置链表的思想是从前向后遍历，把每一个新遍历到的节点加到最前面。
（三）链表融合
void mergeList(ListNode
*& l1
, ListNode
*& l2
){
ListNode
* l1_next
= nullptr;
ListNode
* l2_next
= nullptr;
while(l1
!= nullptr && l2
!= nullptr){
l1_next
= l1
-> next
;
l2_next
= l2
-> next
;
l1
-> next
= l2
;
l2
-> next
= l1_next
;
l1
= l1_next
;
l2
= l2_next
;
}
}
跳出循环条件其实不必如此严苛，但为了程序更鲁棒，也是为了更易读，还是采用这种写法。
总结
看完别忘了点赞哦(人 •͈ᴗ•͈)۶♡♡ 欢迎评论！
