LeetCode 206(Reverse Linked List, Python)

1. 문제 링크

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

Reverse Linked List - LeetCode

 

2. 문제 설명

• linked list인 head가 주어졌을 때, 이를 reverse한 linked list를 반환
• 예시1) head = [1,2,3,4,5] 이면 이를 거꾸로한 [5,4,3,2,1] 의 head를 반환
• 예시2) head = [1,2] 이면, [2,1]의 head를 반환 

3. 처음 풀이

• 난이도 easy인데 linked list가 참 어려워서 결국 스스로 답을 찾진 못했다. 
• None → 1 → 2 → 3 → 4 → 5 를 5 → 4 → 3 → 2 → 1 → None 으로 만드는 방식으로 했는데
  • None에 p, 1에 head, 2에 n이라는 변수를 두고, 
    • 이를 오른쪽으로 한칸씩 이동해가면서 로직을 작성했다.
  • 먼저 head.next = p로 두면 첫 while문에서 1 → None으로 순서가 변경이 되고, 1(head) → None(p)인 상황이 된다.
  • p = head로 다시 바꾸게 되면 1(p) → None가 되고 
  • head = n, n = head.next를 통해 2(head) → 3(n) → 4 → 5 로 커서를 옮긴다.
  • 즉, while문을 한번 돌면 
    • 1(p) → None / 2(head) → 3(n) → 4 → 5 으로 만들어진다.
    • while을 반복하게 되면 
      • 2(p) → 1 → None / 3(head) → 4(n) → 5 
      • 3(p) → 2 → 1 → None / 4(head) → 5(n)
      • 4(p) → 3 → 2 → 1 → None / 5(head) → None(n) 이 된다.
      • while을 head.next가 존재할때까지 반복하므로, 여기서 끝이나고,
    • 마지막에 head.next = p를 두어서 5 → 4 → 3 → 2 → 1 로 만들어서 head를 반환했다.
  • 여기서의 핵심은 앞이나 뒤에 더미 None을 만들고, 3개의 pointer의 노드 위치를 반복해서 움직이며 하나씩 뒤집는것.

# 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]:
        if head is None or head.next is None:
            return head

        p = None
        n = head.next

        while head.next:
            head.next = p
            p = head
            head = n
            n = head.next

        head.next = p

        return head

 

4. 다른 풀이

• 로직은 같으나 
  • while head: 로 돌리면 굳이 while이후에 추가 코드를 작성할 필요가 없고, 
  • head is None, head.next is None처리는 애초에 할 필요가 없었다. 
  • 아래가 좀 더 깔끔히 작성된 코드

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None

        while head:
            nxt = head.next
            head.next = prev
            prev = head
            head = nxt

        return prev

 

5. 배운 점

• 제일 앞이나 뒤에 더미 None을 만드는 아이디어.
• Linked List는 반복해도 뭔가 헷갈리고 어렵다. easy인데 시간을 많이 잡아먹었다... 익숙해지기!