[리트코드] Reverse Linked List(python)

리트코드, Reverse Linked List_연결 리스트 뒤집기

 

TL;DR

• 연결 리스트(Linked List) 문제를 해결할 수 있는지

문제 분석

1. 주어진 연결 리스트를 뒤집은 리스트를 반환하라.

입출력 형태

입출력 예시

 

- 입력으로 주어진 연결 리스트를 뒤집은 연결 리스트를 반환하면 된다.

풀이

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        
        slow, rev = head, None
        
        while slow:
            rev, rev.next, slow = slow, rev, slow.next
            
        return rev

 

- https://firsteast.tistory.com/35 에서 러너(Runner) 기법을 활용한 팰린드롬 연결 리스트 문제를 해결하였다. 러너에서 아이디어를 따와서 문제를 해결하였다.

- slow가 주어진 연결 리스트의 끝까지 도착할 때까지, slow가 있는 연결 리스트를 rev에 넣고, rev.next 현재 rev값을 넣는다. slow는 다음으로 이동한다. 이와 같은 작업을 아래와 같이 살펴볼 수 있다.

    - 예시 1

        1. rev : 1 -> None, slow : 2 -> 3 -> 4 -> 5 -> None

        2. rev : 2 -> 1 -> None, slow : 3 -> 4 -> 5 -> None

        3. rev : 3 -> 2 -> 1 -> None, slow : 4 -> 5 -> None

        4. rev : 4 -> 3 -> 2 -> 1 -> None, slow : 5 -> None

        5. rev : 5 -> 4 -> 3 -> 2 -> 1 -> None, slow : None

    - rev가 반대로 뒤집은 연결 리스트가 된다.

다른 풀이

- 연결 리스트는 제시한 반복적인 방법(iterative) 뿐만 아니라 재귀적인 방법(recursive)으로 풀 수 있다.