题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
/* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ // 思路:发现大量重复类似的代码,所以递归调用 function reverseKGroup(head, k) { if (k == 1 || head == null) { return head; } // 变量说明,pre、cur,逆序操作的双指针,newHead、newEnd,逆序操作之后的新的链头,链尾 let newHead = null; let newEnd = null; let pre = null; let cur = head; // 判断当前一组是否长度小于k,如果是就返回head,这里的head实际上是递归传入的head,除了第一组之外,其实都是newHead let tmpCur = cur; for (let i = 0; i < k; i++) { if (tmpCur == null) { return head } tmpCur = tmpCur.next; } for (let i = 0; i < k; i++) { if (i == 0) { newEnd = cur; // 这里保存一这一组的开头,执行完下面的逆序之后这里就变成了链尾,需要设定他的next为下一组的newHead } // 逆序操作的代码 let nextNode = cur.next; cur.next = pre; pre = cur; cur = nextNode; } // 找到逆序之后的链头 newHead = pre; if (cur != null) { // 此时的cur进入了下一组的链头(未逆序操作的),判断是否递归,此时递归的head是当前的cur。这个递归返回的是那一段的新链头,需要将本段的链尾指向下一段的链头(将一段段的子链表,连接起来) newEnd.next = reverseKGroup(cur, k); } // 返回新的链头 return newHead; } module.exports = { reverseKGroup: reverseKGroup, };