[leetcode] Reverse Linked List

Reverse Linked List

나의 접근법

연결된 리스트를 타고 가면서 지나온 값을 모두 저장한 뒤에 새롭게 리스트를 만들어야겠다고 생각했지만, 리스트가 정말 길 때 for문을 2번 돌아야 해서 비효율적이었다.

다른 사람 풀이

정신차리고 봐야 한다. 1시간은 이 문제만 생각한 거 같다😵‍💫

크게 동작은 (1) 화살표를 반대로 바꾸고 (2) prev와 head를 오른쪽으로 옮기는 과정으로 되어있다.

prev를 None값으로 선언한다.

head.next가 가리키고 있는 것을 prev로 바꿔서 반대쪽을 향하게 한다.

prev = head로 prev의 값을 head로 옮긴다. 왼쪽에 있는 값(prev)이 오른쪽 변수(head)의 위치로 이동한다고 생각하면 과정을 이해하기 편하다. 오른쪽으로 쭉쭉 이동!

head = next_node로 head의 값을 next의 위치로 옮겨준다. 오른쪽으로 이동~!

이러면 while문 한 바퀴가 끝난다. 이 과정을 head != None일 때까지 반복한다.

코드

# Definition for singly-linked list.
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: ListNode = None
        
        while head != None:
            next_node: ListNode = head.next
            head.next = prev
            prev = head
            head = next_node
        
        return prev

리스트의 길이만큼 반복하면 된다. O(N)

참고 자료

Nick White