当前位置： 面试刷题>> K 个一组翻转链表(经典算法150题)
### 题目描述
给定一个单链表，将其按`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
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 示例代码
```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 示例代码
```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`个一组翻转功能，并提供了示例用法来验证其正确性。