[2024] day 82. Leetcode 206. Reverse Linked List

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 21일 (목)
Leetcode daily problem

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/?envType=daily-question&envId=2024-03-21

Problem

하나의 연결형 리스트가 주어질 때, 해당 연결형 리스트 원소를 reverse한 연결형 리스트를 반환한다.

Solution

linked list, recursion

해당 문제는 주어진 연결형 리스트 head의 원소를 거꾸로 뒤집어서 다시 연결형 리스트로 반환하는 문제이다.
포인터를 이용해서 풀어도 되고 재귀를 이용해서 풀어도 되는데 나는 먼저 포인터를 이용해서 풀었다.
먼저 한번 연결형 리스트를 순환하면서 해당 노드를 스택에 넣고,
해당 스택에 있는 원소를 pop하면서 해당 노드를 새로운 노드로 연결해서 만드는 방식으로 풀었다.

Code

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        lst = []
        while head:
            lst.append(head)
            head = head.next

        head = dummy
        while lst:
            node = lst.pop()
            head.next = ListNode(node.val)
            head = head.next

        return dummy.next

Complexicity

시간 복잡도

주어진 연결형 리스트를 탐색하면서 O(n)이 소요되고, 연결형 리스트를 담은 스택을 한번 더 탐색하면서 새로운 연결형 리스트를 생성하므로 O(n)이 소요된다.
최종 시간복잡도는 O(n)이다.

공간 복잡도

연결형 리스트를 탐색하면서 해당 노드를 리스트에 넣어 보관하므로 O(n)의 공간복잡도가 필요하다.
추후에 새로운 연결 리스트를 만드는 과정도 O(n)의 공간을 필요로 하므로 최종 공간복잡도는 O(n)이다.

---

재귀로 푸는 방법

• 사실 재귀로 푸는 방법이 아직 손에 익지않아서 해당 문제를 재귀로 푸는 것은 바로 떠오르지 않지만
  재귀로 푼다면 아래와 같이 해결 할 수 있다.

연결형 리스트를 탐색할 때, 연결형 리스트의 다음 노드를 끊고 해당 노드를 다른 곳에 할당하고
다른 곳에 할당한 노드를 연결하는 작업을 계속해서 반복한다.
a,b = b,a swap 할때 temp를 두고 a,b를 바꾸는 작업과 유사한 작업으로 해결한다고 생각하면 된다.

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, head

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

해당 코드의 시간복잡도는 연결 리스트의 모든 노드를 반복하며 현재 노드를 이전 노드와 연결을 끊고, 이전 노드를 업데이트한다. 연결 리스트의 길이에 비례하므로 O(n)의 시간이 소요된다.
해당 코드의 공간복잡도는 prev, cur, nxt의 변수만 사용되고 각자 계속 임의의 값이 한 번씩 할당되므로 공간복잡도는 O(1)이다.