[Leetcode 아주 상세한 문제풀이] 206. Reverse Linked List - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 206번 문제 Reverse Linked List 다.

우선 문제를 살펴보자.

 

리트코드 206번 문제 Reverse Linked List 링크

Reverse Linked List - LeetCode

Reverse Linked List - LeetCode

 

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

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:
Input: head = [1,2]
Output: [2,1]

Example 3:
Input: head = []
Output: []
 
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

 

 

문제 설명

문제를 한 번 살펴보자. Singly-linked 리스트가 주어졌다. 이를 반대 순서로 리턴하라는 것이다. 문제 예시 1번에서 보는 것처럼 [1,2,3,4,5]라는 리스트는 singly-linked 되어있다. 여기서 singly-linked라는 것은 그림에서 보는 것처럼 하나씩 차례대로 연결되어 있다는 뜻이다. 예를 들어 1이 2 이외에 3이나 4와 연결되어 있지 않다는 뜻이다. 이때 주어진 리스트를 반대 순서로 리턴하라는 매우 단순한 문제다. 곧바로 문제를 풀어보자. 

 

 

문제 접근법

이 문제는 보이는 것과 달리 살짝 복잡하다.

최대한 간단한 예시를 들어 설명할테니 잘 따라와주길 바란다.

예를 들어 singly-linked된 [1,2,3]이란 리스트가 있다고 생각해보자.

우리는 이 리스를 반대 순서로 반들어 [3,2,1]로 리턴해야한다.

우리는 3가지 포인터를 이용하는 iterative approach를 이용해 문제를 풀어볼 생각이다.

우선 주어진 리스트의 head부터 탐색해나갈 예정인데, 3가지 포인터 prev, current, next를 순서대로 위치 시킨다.

즉, 첫번째 iteration에서는 current를 1 자리에 놓고, 그 전에 prev를 그 후에 next를 놓는다.

리스트 head 경우 prev에 해당하는 숫자가 없기 때문에 'none'으로 처리된다.

우리는 이 3가지 포인터를 순서대로 오른쪽으로 옮겨나가며 순서를 바꾸는 작업을 할 것이다.

 

3가지 포인터를 위치시킨 후 각 iteration에서 우리가 해야 할 일은 다음과 같다.

1) Next 포인터가 가리키는 값을 다음 노트 (Next node)에 설정한다.

2) 그리고 그 자리 (Next 포인터가 있는 자리)에 Prev 값을 설정한다.

- 이 과정을 통해 우리는 1->2 singly link를 끊어낼 수 있다. 

3) 마지막으로 prev는 current로, current는 next로 포인터를 한 칸씩 오른쪽으로 옮긴다.

이 3가지 스텝을 마치고 나면 아래에서 보는 것처럼 Current node에는 1->none, 그리고 Next node에는 2->3이 남는다.

동일한 과정을 2번 더 iteration하고 나면 아래와 같이 3->2->1->none 순서대로 singly-linked 리스트를 얻을 수 있다.

 

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

우선 singly-linked 리스트를 위한 클래스를 설정해준다 (line 1)

self.val은 현재 값, self.next는 다음 값을 의미한다. (line 2-3)

앞서 설명한 singly-linked 리스트를 반대로 재배열하기 위한 reverseList 함수를 정의한다 (line 6)

3개의 포인터를 설정함에 있어 리스트의 head가 current일 때 바로 전에 해당하는 값 (prev)이 없으므로 none으로 초기화를 시켜준다 (line 7)

그리고 현재 리스트의 head를 current로 설정해준다. (line 8)

기 설명한대로 주어진 리스트를 head부터 차례로 탐색하는데 (line 9)

우선 next 포인터가 가리키는 값을 다음 노트 (Next node)로 옮기고 그 자리에 prev 값을 넣어준다 (line 10-11)

그 후 prev는 current로, current는 next로 오른쪽으로 한 칸씩 옮겨준다. (line 12-13)

마지막에 prev를 리턴해주는데, 리스트의 순서가 바뀌었으므로 prev가 가리키는 값이 새로운 리스트의 head가 된다 (line 14)

앞서 설명은 안했지만 우리는 helper function을 두 개 만들것이다 (line 17)

이는 linked된 리스트를 i) 만들고 ii) 출력하기 위함이다.

만약 입력된 리스트가 비어있다면 고려해줄 것이 업기 때문에 none을 리턴해준다 (line 18-19)

입력된 리스트의 가장 첫번째 인덱스에 해당하는 값을 head로 하고 그 값에 current 포인터를 위치시킨다 (line 20-21)

그리고 그 다음 값부터 for loop를 이용해 탐색하며 서로 연결 시켜준다 (line 22)

마지막엔 head를 리턴해주는데 리스트의 값들이 서로 연결되어 있기 때문이다 (line 23)

두번째 help function은 출력을 위함이다.

Head가 존재하는 한 그 head값 부터 시작해 '->'로 이어지는 연결된 리스트를 출력해준다 ((line 28-31)

 

 

문제 풀이 코드

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev
 
# Helper functions to create and print linked list
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head
 
def print_linked_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("None")
 
# Test
head1 = create_linked_list([1,2,3,4,5])
print_linked_list(reverseList(head1))
 
head2 = create_linked_list([1,2])
print_linked_list(reverseList(head2))
 
head3 = create_linked_list([])
print_linked_list(reverseList(head3))
 

 

 

관련 문제

리트코드 19번 Remove Nth node from end of list 문제 풀이 (링크)

리트코드 21번 Merge two sorted lists 문제 풀이 (링크)

리트코드 23번 Merge K sorted lists 문제 풀이 (링크)

리트코드 141번 Detec cycle in a linked list 문제 풀이 (링크)

리트코드 143번 Reorder list 문제 풀이 (링크)

 

206. Reverse Linked List