LeetCode #206 Обратный связный список

Привет всем👋

Сегодня мы обсуждаем проблему Leetcode #206.

Проблема

Реверсировать односвязный список.

Пример:

Входные данные: 1->2->3->4->5->NULL
Выход: 5->4->3->2->1->NULL

Продолжение:

Связный список можно развернуть либо итеративно, либо рекурсивно. Можете ли вы реализовать оба варианта?

Решение — итеративно.

Используйте указатель, который указывает на узел x, который является головным в начале. На каждой итерации, если у него есть следующий узел y, переместите следующий узел перед текущей головой и обновите указатель головы на y. Если у x нет следующего узла, т.е. он является хвостом, завершите итерацию.


# Python3

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # Iteration approach
        # Run one pointer p in list. At each iteration:
        #     1. n = p.next
        #     2. p.next = n.next, jump cross n
        #     3. n.next = head, n prepend to the front
        #     4. head = n, reassign head

        if head == None:
            return None

        p = head
        while p.next:
            n = p.next
            p.next = n.next
            n.next = head
            head = n

        return head
Вход в полноэкранный режим Выход из полноэкранного режима

Завершение —

временная сложность равна O(n), если n обозначает количество узлов в данном связном списке.

Тривиально, что он использует только O(1) дополнительного пространства.

Решение — рекурсия

# Python3

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # Recursion approach:
        #     take head and reverse list whose head is head.next
        #     then reversely assign the link between them

        if head == None or head.next == None:
            return head

        n = head.next
        h = self.reverseList(n)

        # reverse link
        head.next = None
        n.next = head

        return h
Войдите в полноэкранный режим Выйти из полноэкранного режима

Сложность

При каждом вызове функции требуется всего** O(1) времени для присвоения ссылки**. А всего вызовов n-2, если n обозначает количество узлов в данном связном списке. Таким образом, временная сложность будет равна O(n).

Кроме того, она **использует O(1) дополнительного пространства **в каждом вызове функции, и есть n-2 вызова в стеке вызовов. Следовательно, пространственная сложность также равна O(n).

Спасибо, что прочитали эту статью. Надеюсь, она поможет вам решить эту проблему.
Если вам понравилась статья, просто следуйте за *@coders_village в instagram.

Спасибо
Шивани Тивари
(Разработчик программного обеспечения)

Оцените статью
devanswers.ru
Добавить комментарий