문제 설명

아래와 같은 singly linked list가 주어졌을 때, 역순(reverse)으로 변환해 반환해야 한다.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

문제 출처: https://leetcode.com/problems/reverse-linked-list/

문제 풀이

Follow up에서 요구한 대로 Iterative, Recursive 방법 두 가지를 통해 구현했다.

By Iteration

# 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]:
        prev, cur = None, head

        while cur:
            _next = cur.next # 현재 노드의 다음 노드를 저장해둔다.
            cur.next = prev # 현재 노드의 연결을 전 노드로 바꾼다. (reverse)
            prev = cur # 다음 노드의 연결을 현재 노드로 바꾸기 위해 현재 노드를 prev로 저장.
            cur = _next # 다음 노드로 이동

        reversed_head = prev 

        return reversed_head

By Recursion

# 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 not head: # head가 None이라면 None return (빈 링크드 리스트일 때)
            return None

        new_head = head
        if head.next:
            new_head = self.reverseList(head.next) # 맨 끝 노드가 new head로
            head.next.next = head # 다음 노드의 연결을 자신으로 (reverse)
        head.next = None # tail의 연결을 None으로 (reverse되어서 head가 tail이 된다)

        return new_head

Reference

• NeetCode - Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python