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

복잡성-

n이 이 연결 리스트의 노드 수를 나타내는 경우 시간 복잡도는 O(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이 이 연결 목록의 노드 수를 나타내는 경우 n-2 호출이 있습니다. 따라서 시간 복잡도는 O(n)이 됩니다.

또한 **각 함수 호출에서 **O(1) 추가 공간 **을 사용하고 호출 스택에 n-2 호출이 있습니다. 따라서 공간 복잡도도 O(n)입니다.

이 기사를 읽어 주셔서 감사합니다. 이 문제를 해결하는 데 도움이 되기를 바랍니다.
글이 마음에 든다면 인스타그램에서 *@coders_village를 팔로우하세요 *

감사합니다
시바니 티와리
(소프트웨어 개발자)