리트코드 - 206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/

Reverse Linked List - LeetCode

single linked list가 주어졌을 때 이를 역순으로 변환하여 반환하는 문제이다.

 

각 노드를 반복하면서 노드의 next 포인터를 이전 노드로 업데이트하는 과정을 수행하면서 문제를 해결할 수 있다.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newNode = None  # O(1)
        currNode = head  # O(1)
        
        while currNode:  # O(n), 여기서 n은 리스트의 길이
            nextNode = currNode.next  # O(1)
            currNode.next = newNode  # O(1)

            newNode = currNode  # O(1)
            currNode = nextNode  # O(1)
        
        return newNode  # O(1)

 

모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이 된다

입력 리스트 외에 추가적인 공간 사용이 없고. 추가적인 리스트나 데이터 구조를 사용하지 않고, 입력 리스트의 노드들만 재배열하기 때문에 공간 복잡도는 O(1)이 된다.