Heading

25.K 个一组翻转链表 ♥ (opens new window)

Tags: algorithms facebook microsoft linked-list

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Hard (63.34%)
• Likes: 785
• Dislikes: -
• Total Accepted: 113K
• Total Submissions: 177.9K
• Testcase Example: '[1,2,3,4,5]\n2'

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

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

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

 

示例：

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

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

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

说明：

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

/*
 * @lc app=leetcode.cn id=25 lang=javascript
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    const hair = new ListNode(0, head);
    let Insert = hair;
    let p = Insert.next, q, step, r;
    while (p) {
        step = k
        q = p
        while (q && step-- > 0) {
            q = q.next
        }
        if (step <= 0) {
            let tmp = null
            while (p !== q) {
                if (Insert.next === p) {
                    tmp = p //下一个插入点
                    p = p.next
                    continue;
                }
                r = p.next
                p.next = Insert.next;
                Insert.next = p
                p = r
            }
            Insert = tmp
            Insert.next = q
        } else {
            return hair.next
        }
    }
    return hair.next
};
// @lc code=end