|
| 1 | +#LeetCode 第 25 号问题：K 个一组翻转链表 |
| 2 | + |
| 3 | +>本文首发于公众号「图解面试算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。 |
| 4 | +> |
| 5 | +>同步博客：https://www.algomooc.com |
| 6 | +
|
| 7 | +题目来源于 LeetCode 上第 25 号问题：K 个一组翻转链表。题目难度为 Hard |
| 8 | + |
| 9 | +###题目描述 |
| 10 | + |
| 11 | +给你一个链表，每*k* 个节点一组进行翻转，请你返回翻转后的链表。 |
| 12 | + |
| 13 | +*k* 是一个正整数，它的值小于或等于链表的长度。 |
| 14 | + |
| 15 | +如果节点总数不是*k* 的整数倍，那么请将最后剩余的节点保持原有顺序。 |
| 16 | + |
| 17 | +**示例:** |
| 18 | + |
| 19 | +给你这个链表：`1->2->3->4->5` |
| 20 | + |
| 21 | +当*k* = 2 时，应当返回:`2->1->4->3->5` |
| 22 | + |
| 23 | +当*k* = 3 时，应当返回:`3->2->1->4->5` |
| 24 | + |
| 25 | +**说明:** |
| 26 | + |
| 27 | +- 你的算法只能使用常数的额外空间。 |
| 28 | +-**你不能只是单纯的改变节点内部的值**，而是需要实际进行节点交换。 |
| 29 | + |
| 30 | +###题目解析 |
| 31 | + |
| 32 | +这道算法题可以说是[两两交换链表中的节点](https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0024-Swap-Nodes-in-Pairs/Article/0024-Swap-Nodes-in-Pairs2.md) 的升级版, 区别就是反转的子链表节点个数变成了自定义. |
| 33 | + |
| 34 | +总体思路还是一样的, 具体可以分为两个处理模块: |
| 35 | + |
| 36 | +1. 根据*k* 划分若干个需要反转的子链表, 连接反转后的子链表, 最后不足*k* 的子链表保持不变 |
| 37 | + |
| 38 | +- 设置哨兵`dummy` 指向`head` , 为了能找到反转后的链表头结点; |
| 39 | + |
| 40 | +- 循环*k* 确定需要 反转子链表 的范围: |
| 41 | + |
| 42 | +- 循环完成, 确定子链表可以反转 |
| 43 | + |
| 44 | + 假设*A* ,*B* 子链表邻接且都可以反转 |
| 45 | + |
| 46 | +- 指针`start` 指向*A* 的头结点,`end` 指向*A* 的尾结点,`nxt` 指向*B* 的头结点 |
| 47 | +-`start -> end` 反转后,`start` 变成了 A 的尾结点,`start -> next = nxt` , 反转后的*A* 链表指向了*B* |
| 48 | +- 重置`start` 为*B* 的头节点,`end` 为*B* 的尾结点,`nxt` 为下一个子链表头节点, 反转*B* 链表 |
| 49 | +- 重复上面动作, 知道 循环终止 |
| 50 | + |
| 51 | +- 循环终止, 剩余节点不足*k* , 终止反转, 返回链表 |
| 52 | + |
| 53 | +2. 反转子链表 |
| 54 | + |
| 55 | + 假设子链表前三个节点为*a*,*b*,*c* ,设置指针`pre`,`cur`,`nxt` , 初始化`pre` 值为`null`,`cur` 值为*a* ,`nxt` 值为*a* , 这三个指针位置不变且相邻 |
| 56 | + |
| 57 | + 终止条件:`cur` 不为空 |
| 58 | + |
| 59 | + 将当前节点的指针指向上一个节点 |
| 60 | + |
| 61 | +1.`cur` 指向`nxt` (`nxt` 值为*b* ) |
| 62 | +2.`cur` 指向`pre` (`cur` 指向`null` ) |
| 63 | +3.`cur` 赋值给`pre` (`pre` 值为*a* ) ,`nxt` 赋值给`cur` (`cur` 值为*b* ) |
| 64 | +4. 在执行 步骤`1` (`nxt` 值为*c* , 到此相当于`pre`,`cur` ,`nxt` 指向依次向后移动`1` 位 ) |
| 65 | +5. 重复上面动作 |
| 66 | + |
| 67 | +###动画描述 |
| 68 | + |
| 69 | +<imgsrc="../Animation/Animation.gif"alt="Animation"style="zoom:150%;" /> |
| 70 | + |
| 71 | +###参考代码 |
| 72 | + |
| 73 | +####反转链表 |
| 74 | + |
| 75 | +```javascript |
| 76 | +/** |
| 77 | + * JavaScript 描述 |
| 78 | + * 反转区间 [start, end) 的元素, 注意不包含 end |
| 79 | +*/ |
| 80 | +functionreverse(start,end) { |
| 81 | +let pre=null, |
| 82 | + cur= start, |
| 83 | + nxt= start; |
| 84 | +while (cur!= end) { |
| 85 | + nxt=cur.next; |
| 86 | +// 逐个节点反转 |
| 87 | +cur.next= pre; |
| 88 | +// 更新指针位置 |
| 89 | + pre= cur; |
| 90 | + cur= nxt; |
| 91 | + } |
| 92 | +// 反转后的头结点, start 移到了最后, end 没有发生改变 |
| 93 | +return pre; |
| 94 | +}; |
| 95 | +``` |
| 96 | + |
| 97 | +####递归解法 |
| 98 | + |
| 99 | +```javascript |
| 100 | +/** |
| 101 | + * JavaScript 描述 |
| 102 | + * 递归 |
| 103 | +*/ |
| 104 | +varreverseKGroup=function(head,k) { |
| 105 | +if (head==null) { |
| 106 | +returnnull; |
| 107 | + } |
| 108 | +let start, end; |
| 109 | + start= end= head; |
| 110 | +for (let i=0; i< k; i++) { |
| 111 | +// 不足 k 个，不需要反转 |
| 112 | +if (end==null) { |
| 113 | +return head; |
| 114 | + } |
| 115 | + end=end.next; |
| 116 | + } |
| 117 | +// 反转前 k 个元素, 不包含 end |
| 118 | +let reverseHead=reverse(start, end); |
| 119 | +// 递归反转后面k个元素 , 并前后连接起来 |
| 120 | +start.next=reverseKGroup(end, k); |
| 121 | +return reverseHead; |
| 122 | +}; |
| 123 | +``` |
| 124 | + |
| 125 | +####迭代解法 |
| 126 | + |
| 127 | +```javascript |
| 128 | +/** |
| 129 | + * JavaScript 描述 |
| 130 | + * 迭代 |
| 131 | +*/ |
| 132 | +varreverseKGroup=function(head,k) { |
| 133 | +let dummy=newListNode(0); |
| 134 | +dummy.next= head; |
| 135 | +let pre, start ,end, nxt; |
| 136 | + pre= start= end= nxt= dummy; |
| 137 | +while (end.next!=null) { |
| 138 | +for (let i=0; i< k&& end!=null; i++) { |
| 139 | + end=end.next; |
| 140 | + } |
| 141 | +if (end==null) { |
| 142 | +// 不足 k 个, 跳出循环 |
| 143 | +break; |
| 144 | + } |
| 145 | + start=pre.next; |
| 146 | + nxt=end.next; |
| 147 | +// 反转前 k 个元素, 不包含 nxt |
| 148 | +pre.next=reverse(start, nxt); |
| 149 | +// 链接后面的链表 |
| 150 | +start.next= nxt; |
| 151 | +// pre , end 重置到 下一个 k 子链表 |
| 152 | + pre= start; |
| 153 | + end= pre; |
| 154 | + } |
| 155 | +returndummy.next; |
| 156 | +}; |
| 157 | +``` |
| 158 | + |
| 159 | +###复杂度分析 |
| 160 | + |
| 161 | +- 时间复杂度:**O( nk )** , 最好情况 O( n ), 最坏情况 O( n^2 ) |
| 162 | + |
| 163 | +- 空间复杂度:**O( 1 )** |
| 164 | + |
| 165 | + |
| 166 | + |
| 167 | + |
| 168 | + |
| 169 | + |