LeetCode25. K 个一组翻转链表🌟🌟🌟困难
问题描述
原文链接：25. K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
代码实现
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 1-》2-〉3-》4-〉5。K = 2;
ListNode temp = head;
//1-》2， 3-〉4-》4
for(int i = 1; temp != null && i < k; i++ ){
temp = temp.next;
}
if(temp == null){
return head;
}
// t指向第二部分:t->3->4->5->null. head->1->2->null;
ListNode t = temp.next;
temp.next = null;
// newhead->2->1->null;
ListNode newHead = reverseList(head);
//newTemp->3->4->5->null
ListNode newTemp = reverseKGroup(t, k);
// 拼接
head.next = newTemp;
return newHead;
}
ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode result = reverseList(head.next);
head.next.next = head;
head.next = null;
return result;
}
}
Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
# 1-》2-〉3-》4-〉5。K = 2;
temp = head
#1-》2， 3-〉4-》4
for i in range(1, k):
if temp is None:
return head
temp = temp.next
if temp is None:
return head
# t指向第二部分:t->3->4->5->null. head->1->2->null;
t = temp.next
temp.next = None
# newhead->2->1->null;
newHead = self.reverseList(head)
#newTemp->3->4->5->null
newTemp = self.reverseKGroup(t, k)
# 拼接
head.next = newTemp
return newHead
def reverseList(self, head):
if head is None or head.next is None:
return head
result = self.reverseList(head.next)
head.next.next = head
head.next = None
return result
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* temp = head;
for(int i = 1; temp != nullptr && i < k; i++ ){
temp = temp->next;
}
if(temp == nullptr){
return head;
}
ListNode* t = temp->next;
temp->next = nullptr;
ListNode* newHead = reverseList(head);
ListNode* newTemp = reverseKGroup(t, k);
head->next = newTemp;
return newHead;
}
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* result = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return result;
}
};
Go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
temp := head
for i := 1; temp != nil && i < k; i++ {
temp = temp.Next
}
if temp == nil {
return head
}
t := temp.Next
temp.Next = nil
newHead := reverseList(head)
newTemp := reverseKGroup(t, k)
head.Next = newTemp
return newHead
}
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
result := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return result
}