25. Набор из K перевернутых связанных списков.

LeetCode

Вам дан связанный список, и каждая группа k узлов перевернута, и, пожалуйста, верните перевернутый связанный список.

k — положительное целое число, значение которого меньше или равно длине связанного списка.

Если общее количество узлов не является целым числом, кратным k, оставьте последние оставшиеся узлы в их первоначальном порядке.

Передовой:

Вы можете разработать алгоритм, используя только постоянное дополнительное пространство для решения этой проблемы? Вы не можете просто изменить внутренние значения узла, но вам нужно фактически обменять узел.

image.png

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

Решение первое

Прежде чем смотреть ответ, напишите его сами. Решение похоже на замену узлов в связанном списке попарно, потому что рекурсия не может использоваться, поскольку требуется постоянное дополнительное пространство, поэтому используется итеративное решение.

Основная идея: каждый раз, когда k узлов из связанного списка вынимаются и сохраняются в массиве, в массиве выполняется операция переворачивания узлов.

def reverseKGroup1(head, k):
    """迭代，解法和两两交换链表中的节点类似"""
    if k == 1: return head  # 如果k=1，就直接返回原链表

    dummy = ListNode()
    dummy.next = head  # 声明一个哑节点，指向链表的头节点
    temp = dummy  # 每次翻转temp后面的k个节点
    arr = []  # 用来记录链表中的节点

    while temp:
        for i in range(k):  # 每次取出链表中的k个节点
            arr.append(head)
            head = head.next
            if head is None: break  # 如果节点为空了，直接跳出这层for循环

        if len(arr) < k:  # 如果数组长度小于k，那么就不需要交换节点，直接跳出while循环
            break

        last_node = arr[-1].next  # 用来记录剩下的未交换的节点

        for i in range(k):  # 在数组中翻转节点
            if i == 0:  # 第一步让temp指向最后一个节点
                temp.next = arr[-1]
            arr[-i].next = arr[-(i + 1)]  # 翻转中间的节点，令后一个节点指向前一个节点
            if i == k - 1:  # 最后一步，让翻转后的最后一个节点指向剩下的未交换的节点
                arr[-(i + 1)].next = last_node

        temp = arr[0]  # 将temp指向交换过后的最后一个节点
        if temp.next is None: break  # 如果最后一个节点的next为空，则结束循环
        arr.clear()  # 每次循环结束后，清空数组，用于存储下次循环的k个节点

    return dummy.next
Анализ сложности
  • Временная сложность: O(n).
  • Пространственная сложность: O(1), нам нужно только создать постоянное количество переменных.

Я чувствую, что перевернутый подссылочный список в официальном ответе непрост для понимания, поэтому я не буду его публиковать.Если вам интересно, вы можете прочитать его самостоятельно.

Официальный ответ Ликоу

Категории