Итеративное решение для обратного связанного списка в наборах k

Question

Учитывая односвязный список, я пытаюсь повернуть k узлов за раз по всему списку. Так, если k = 2, 1 -> 2 -> 3 -> 4 -> 5 -> 6 превратится в 2 -> 1 -> 4 -> 3 -> 6 ->5 . Предполагается, что k всегда является фактором длины списка (длина списка делится на k).

Я пытаюсь решить эту проблему, используя итерационный подход , а нерекурсивный. Я пытаюсь проанализировать список как наборы из k узлов и повернуть их до конца списка. Это мой код

def reverseList(A, B): # param A : head node of linked list, param B : integer, return the head node in the list
    if B < 2:
        return A
    dummy = ListNode('dummy')
    dummy.next = A
    prev, behind = dummy, A
    while behind:
        ahead = behind
        for i in range(B-1):
            ahead = ahead.next
        new_behind = reverse_list(behind, ahead)
        prev.next = ahead
        behind.next = new_behind
        behind = behind.next
    return dummy.next

Функция reverse_list переворачивает список от начальных до конечных узлов набора ak и возвращает узел в начале нового k набора узлов (новый начальный узел)

def reverse_list(start, end):
    prev, curr = None, start
    while prev is not end:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return curr

Определение класса ListNode

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

Когда заданы значения A = [6 -> 10 -> 0 -> 3 -> 4 -> 8] и B = 3, вывод 8 -> 4 -> 3. Что именно я пропускаю или пропускаю? Любая помощь с благодарностью.

Answer 1

Для каждой итерации вы должны указать следующий узел текущего узла на следующий узел следующего узла, затем указать следующий узел следующего узла на головной узел, а затем направить головной узел на следующий узел, чтобы завершить обращение заданного количества узлов. Затем назначьте текущий узел в качестве нового заголовка, повторяйте выше, пока следующий узел заголовка не будет None:

def reverseList(A, B):
    head = A
    while head.next:
        node = head.next
        for _ in range(B - 1):
            next_node = node.next
            if next_node:
                node.next = next_node.next
                next_node.next = head.next
                head.next = next_node
        head = node
    return A

Демо: https://repl.it/@blhsing/ElatedSurefootedFilesize

Answer 2

Я понял, какую ошибку я совершил. Я не обновлял указатель «предыдущий» при обновлении указателя «позади». Это должно было быть

prev = позади

После получения указателей сзади и вперед это должен быть блок кода в цикле while в функции reverseList

new_behind = reverse_list(behind, ahead)
prev.next = ahead
behind.next = new_behind
prev = behind
behind = behind.next