206. Reverse Linked List

Reverse Linked List - LeetCode

1. Stack을 사용한 풀이

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        stack = []
        cur = head
        while cur:
            stack.append(cur)
            cur = cur.next
        new_head = stack.pop()
        cur = new_head
        while stack:
            cur.next = stack[-1]
            cur = cur.next
            stack.pop()
        cur.next = None
        return new_head

스택에 노드를 삽입하고 빼면서 next값을 갱신하면서 주어진 연결 리스트를 뒤집었다.

 

 

2. Pointer를 사용한 (나름) 우아한 풀이

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

이전에 풀었던 문제를 응용했다. 확실히 이젠 구조가 눈에 들어와서 바로 작성할 수 있었다.