题目描述

给定一个单链表，将其按k个一组进行翻转，返回翻转后的链表。如果链表的节点数不是k的整数倍，那么最后剩余的节点将保持原样。

示例：

给定链表 1->2->3->4->5 和 k = 2，应当返回 2->1->4->3->5。

给定链表 1->2->3->4->5 和 k = 3，应当返回 3->2->1->4->5。

PHP 示例代码

<?php

class ListNode {
    public $val;
    public $next;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function reverseKGroup($head, $k) {
    if ($head == null || $k == 1) return $head;

    $dummy = new ListNode(0);
    $dummy->next = $head;
    $prev = $dummy;

    while ($head) {
        $tail = $prev;

        // 检查剩余节点是否足够k个
        for ($i = 0; $i < $k; $i++) {
            $tail = $tail->next;
            if ($tail == null) {
                // 剩余节点不足k个，直接返回结果
                return $dummy->next;
            }
        }

        $next = $tail->next;
        $head, $tail = reverseBetween($head, $tail);

        // 重新连接链表
        $prev->next = $head;
        $tail->next = $next;

        $prev = $tail;
        $head = $next;
    }

    return $dummy->next;
}

function reverseBetween($head, $tail) {
    $prev = null;
    $curr = $head;

    while ($curr != $tail) {
        $next = $curr->next;
        $curr->next = $prev;
        $prev = $curr;
        $curr = $next;
    }

    return [$tail, $head];
}

// 示例用法
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$k = 2;
$result = reverseKGroup($head, $k);

// 辅助函数来打印链表
function printList($node) {
    while ($node != null) {
        echo $node->val . " ";
        $node = $node->next;
    }
    echo "\n";
}

printList($result);  // 输出: 2 1 4 3 5
?>

Python 示例代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    if not head or k == 1:
        return head

    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while head:
        tail = prev
        for _ in range(k):
            tail = tail.next
            if not tail:
                return dummy.next

        next_head = tail.next
        head, tail = reverse_between(head, tail)

        prev.next = head
        tail.next = next_head
        prev = tail
        head = next_head

    return dummy.next

def reverse_between(head, tail):
    prev = None
    curr = head
    while curr != tail:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return tail, head

# 示例用法
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

k = 2
result = reverseKGroup(head, k)

# 辅助函数来打印链表
def print_list(node):
    while node:
        print(node.val, end=" ")
        node = node.next
    print()

print_list(result)  # 输出: 2 1 4 3 5

JavaScript 示例代码

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function reverseKGroup(head, k) {
    if (!head || k === 1) return head;

    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;

    while (head) {
        let tail = prev;

        // 检查剩余节点是否足够k个
        for (let i = 0; i < k; i++) {
            tail = tail.next;
            if (!tail) return dummy.next;
        }

        const nextHead = tail.next;
        [head, tail] = reverseBetween(head, tail);

        // 重新连接链表
        prev.next = head;
        tail.next = nextHead;

        prev = tail;
        head = nextHead;
    }

    return dummy.next;
}

function reverseBetween(head, tail) {
    let prev = null;
    let curr = head;

    while (curr !== tail) {
        const nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }

    return [tail, head];
}

// 示例用法
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

const k = 2;
const result = reverseKGroup(head, k);

// 辅助函数来打印链表
function printList(node) {
    let current = node;
    while (current) {
        console.log(current.val);
        current = current.next;
    }
}

printList(result); // 输出: 2 1 4 3 5

以上三个示例均实现了给定链表的k个一组翻转功能，并提供了示例用法来验证其正确性。