25. Reverse Nodes in k-Group
leetcode hard
#csharp#hard#leetcode#linked-list#queue
Task
Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.
Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.
C# solution
matched/originalpublic class Solution
{
//https://leetcode.com/problems/reverse-linked-list-ii/
private void ReverseList(ListNode head, int m, int n, out ListNode groupHead)
{
var curr = head.next;
var inputHead = head;
int count = n - m;
int idx = 0;
while (idx < count)
{
inputHead.next = curr.next;
curr.next = head;
head = curr;
curr = inputHead.next;
idx++;
}
groupHead = head;
}
public ListNode ReverseKGroup(ListNode head, int k)
{
if (head == null)
{
return null;
}
int count = 0;
ListNode curr = head;
while (curr != null)
{
count++;
curr = curr.next;
}
ListNode res = null;
ListNode prev = null;
curr = head;
int idx = 0;
while (true)
{
if (idx + k - 1 >= count)
{
res = res ?? head;
break;
}
ReverseList(curr, idx, idx + k - 1, out ListNode groupHead);
curr = groupHead;
if (prev != null)
{
prev.next = groupHead;
}
for (int i = 0; i < k; i++)
{
prev = curr;
curr = curr.next;
}
res = res ?? groupHead;
idx += k;
}
return res;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
//https://leetcode.com/problems/reverse-linked-list-ii/
private void ReverseList(ListNode head, int m, int n, out ListNode groupHead)
{
var curr = head.next;
var inputHead = head;
int count = n - m;
int idx = 0;
while (idx < count)
{
inputHead.next = curr.next;
curr.next = head;
head = curr;
curr = inputHead.next;
idx++;
}
groupHead = head;
}
public ListNode ReverseKGroup(ListNode head, int k)
{
if (head == null)
{
return null;
}
int count = 0;
ListNode curr = head;
while (curr != null)
{
count++;
curr = curr.next;
}
ListNode res = null;
ListNode prev = null;
curr = head;
int idx = 0;
while (true)
{
if (idx + k - 1 >= count)
{
res = res ?? head;
break;
}
ReverseList(curr, idx, idx + k - 1, out ListNode groupHead);
curr = groupHead;
if (prev != null)
{
prev.next = groupHead;
}
for (int i = 0; i < k; i++)
{
prev = curr;
curr = curr.next;
}
res = res ?? groupHead;
idx += k;
}
return res;
}
}Java solution
matched/originalpublic ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pointer = dummy;
while (pointer != null) {
ListNode node = pointer;
for (int i = 0; i < k && node != null; i++) node = node.next;
if (node == null) break;
// reverse the k nodes
ListNode prev = null, curr = pointer.next;
for (int i = 0; i < k; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
ListNode tail = pointer.next;
tail.next = curr;
pointer.next = prev;
pointer = tail;
}
return dummy.next;
}Python solution
matched/originalclass Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if k == 1:
return head
# sets first.next as last.next, and others next immediately preceding
# sets pre_first.next or head to point to the new first
def reverse(first, last, pre_first):
nonlocal head
# take care of link to new first node
if pre_first:
pre_first.next = last
else:
head = last
prev, curr = first, first.next
first.next = last.next # take care of link to remaining nodes
for _ in range(k-1):
curr.next, prev, curr = prev, curr, curr.next
count = 1
curr = first = head
pre_first = None
while curr:
if count == k:
# we have reached the kth node, now it's time to reverse and reset
reverse(first, curr, pre_first)
pre_first = first
curr, first = first.next, first.next
count = 1
else:
curr = curr.next
count += 1
return headGo solution
matched/originalfunc reverseKGroup(head *ListNode, k int) *ListNode {
top := &ListNode{
Next: head,
}
track := top
for track.Next != nil {
last, after := reverse(track.Next, k)
if last == nil {
return top.Next
}
track.Next.Next = after
track.Next, track = last, track.Next
}
return top.Next
}
func reverse(n *ListNode, remaining int) (last, after *ListNode) {
if remaining == 1 {
return n, n.Next
}
if n.Next == nil {
return nil, nil
}
last, after = reverse(n.Next, remaining-1)
if last == nil {
return nil, nil
}
n.Next.Next = n
return
}Explanation
1. ReverseList: Это приватный метод, который реализует обращение части связанного списка между позициями m и n. Он обновляет указатель головы группы groupHead, пройдя по списку и меняя указатели в нужной последовательности.
2. ReverseKGroup: Это публичный метод, который реверсирует группы узлов по k элементов в связанном списке. Он сначала определяет общее количество узлов в списке, затем поочередно вызывает ReverseList для групп узлов длиной k. После завершения обработки всех групп он возвращает новую голову списка.
Общий подход заключается в том, что ReverseList изменяет указатели узлов для обращения части списка, а ReverseKGroup последовательно применяет ReverseList для групп узлов длиной k и обновляет указатели в соответствии с этим. Код решает задачу обращения групп узлов в связанном списке.