题目
25. K 个一组翻转链表
解题思路
直接实现反转K个一组翻转链表可能非常困难,但是可以分成长度为K的子串,每一个字串分别反转并拼接,最后返回即可。
反转链表
反转链表很容易实现,可以通过递归/迭代的形式实现。
这里采用的是判断 递归 + 是否为null为basecase 实现
1 2 3 4 5 6 7
| function reverse(head: ListNode | null): ListNode | null { if (head === null || head.next === null) return head; const prev = reverse(head.next); head.next.next = head; head.next = null; return prev; }
|
反转K个
分析可以发现,整体的过程就可以分解成长度为 K
的部分字串,所以明显可以使用递归来实现。
- 遍历当前的链表,如果长度不足
k
,则直接返回头节点,这里需要注意的是 if
判断条件需要放在p.next前还是后的问题
- 保留后驱节点以及设置满足反转的basecase,即记录
successor
和设置 p.next = null
- 反转当前长度为
k
的字串,得到新的头节点
- 拼接
当前的最新尾节点
和 下一个
最新的头节点
- 返回最新的头节点
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
function reverseKGroup(head: ListNode | null, k: number): ListNode | null { if (head === null) return head; let p = head; for (let i = 1; i < k; i++) { p = p.next; if (p === null) return head; } let successor = p.next; p.next = null; const newHead = reverse(head); head.next = reverseKGroup(successor, k); return newHead; }
function reverse(head: ListNode | null): ListNode | null { if (head === null || head.next === null) return head; const prev = reverse(head.next); head.next.next = head; head.next = null; return prev; }
|
链接
CSDN:25. K 个一组翻转链表 | 链表 | 递归 | 子问题分解_一抹阳光&的博客
掘金:25. K 个一组翻转链表 | 链表 | 递归 | 子问题分解