25.K 个一组翻转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

• 25.K 个一组翻转链表

  • 题目描述

  • 原题

    • 思路

    • 代码

  • 变形 1

    • 题目修改

    • 思路

    • 代码

  • 变形 2

    • 题目修改

    • 思路

    • 代码

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。



示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5



说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

原题

思路

遍历链表，用一个计数器 i 来记录当前是第几个节点，当 i 等于 k 的倍数时，将 i 之前的这段链表进行反转，也就是调用一下 reverseBetween(ithNode, i - k + 1, i) 就行，把反转后的链表插回原来的位置，然后继续遍历。

代码

JavaScript Code

// 不想写

变形 1

题目修改

将原题中

“如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序”

改为：

“如果节点总数不是 k 的整数倍，那么请将最前面剩余的节点保持原有顺序”

思路

先遍历一次链表找到剩余节点的个数(用一个 counter 记录，数到 k 就归零)，也就是 len % k，然后从第 len % k + 1 个节点进行 k 个一组的反转。

代码

JavaScript Code

// 不想写

变形 2

题目修改

将原题中

“如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序”

改为：

“如果节点总数不是 k 的整数倍，那么请将最后剩余的节点作为一组进行反转”

思路

跟92.反转链表 II的思路有点像，都是反转链表中的一段，不过这题是以 K 个节点为一组地反转。

大概思路是，用一个计数器 i 记录当前是第几个节点，如果 i 是 0 或者 K 的倍数的话，说明接下来的 K 个节点是一组，对它们进行反转操作就行。

代码

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    if (!head || !head.next || k <= 1) return head;

    const dummy = new ListNode(null);
    dummy.next = head;

    let prev = dummy,
        cur = prev.next;

    let i = 0;
    while (cur) {
        i++;
        if (i % k === 0) {
            prev = cur;
            cur = prev.next;
        }
        if (!cur || !cur.next) break;

        const temp = cur.next;
        cur.next = temp.next;
        temp.next = prev.next;
        prev.next = temp;
    }
    return dummy.next;
};