[LeetCode] #206. Reverse Linked List

#206. 역순 연결 리스트

문제

문제 링크
아래의 그림과 같이 singly linked list 1개가 주어졌을 때, 주어진 연결 리스트를 역순으로 만들어 반환하자.

코드

github

class Solution:
    def reverseList(self, head):
        prev, curr = None, head

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

풀이

이 문제는 재귀 또는 반복을 사용해 풀 수 있다. 나는 반복을 사용해 풀었다.

head-> 노드1-> 노드2-> 노드3으로 이루어진 연결 리스트가 있다.
아무것도 가리키지 않는 prev와 head를 가리키는 curr를 만든다.

1) 노드1-> 노드2 연결을 저장한다.
연결을 바로 끊어야 하지만, 3)에서 다음 노드의 정보를 알아야 이동할 수 있기 때문에 다음 노드의 정보를 여기서 저장한다.
2) 노드1을 가리키던 curr가 None인 prev를 가리키도록 만든다.
3) prev, curr을 다음 노드로 이동시킨다.
4) curr이 존재하지 않을 때까지 다음 노드로 이동하면서 반복한다.

참고:
NeetCode