[DSA][Linked List] 01. Reverse Linked List

LeetCode 206

 

01. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

 

[질문하기]

- 빈 리스트나 노드가 하나뿐인 경우에는 어떻게 처리하나요?

- 연결 리스트가 순환(cycle)을 포함할 가능성도 있나요?

 

 

[아이디어]

- 다음 노드를 미리 저장해 둔 후 연결 관계를 새롭게 하고, prev, cur를 한 칸씩 이동한다.

 

 

[풀이 1] Linked List

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prevNode,curNode = None, head # 시작을 잘 잡아야 한다.

        while curNode:
            nextNode = curNode.next
            curNode.next = prevNode
            prevNode = curNode
            curNode = nextNode
        
        return prevNode

만약 리스트 뒤집기를 prevNode, curNode = head, head.next로 하면 시작 prevNode가 curNode를 가리키고 있는 상태로 curNode는 prevNode를 가리키기 때문에 (reverse 하면 None을 가리켜야 함) 무한 루프에 빠지게 된다.

변수 설정이 처음엔 헷갈릴 수 있지만, 현재 노드의 다음 노드를 미리 저장해두고, 현재 노드가 이전 노드를 가리키게 만든다음, prev와 cur을 각각 cur과 cur.next로 한 칸씩 이동시킨다는 흐름을 기억하면 된다. 

 

⏱️ 시간복잡도

리스트의 각 노드를 한 번씩 순회하면서 .next 포인터를 바꾸므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

prevNode, curNode, nextNode 같은 고정된 변수만 사용하므로 공간 복잡도는 O(1)이다.