LinkedList : Reverse Linked List

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

Reverse Linked List - LeetCode

 

linked list를 뒤집는 문제다.

리스트를 순회하면서 각 노드가 가리키는 값을 이전 노드로 바꿔야된다.

그러므로 노드를 순회할 변수와 그 이전 노드를 저장할 변수가 필요하다.

 

# 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:
            return head

        prev = None
        cur = head

        while cur and cur.next:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        cur.next = prev

        return cur

 

시간 복잡도는 O(N)

공간 복잡도는 O(1)

 

# 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]:
        def rec(node, prev):
            node_next = node.next
            node.next = prev
            if not node_next: return node
            return rec(node_next, node)
        return None if head is None else rec(head, None)

recursive solution이다.

재귀 콜스택때문에 공간복잡도가 O(N)으로 늘었다.

 

 

다른 사람들의 많은 투표를 받은 솔루션은 어떨까?

1. Iterative Solution

class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
    prev = None
    while head:
        curr = head
        head = head.next
        curr.next = prev
        prev = curr
    return prev

 

2. Recursive Solution

class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
    return self._reverse(head)

def _reverse(self, node, prev=None):
    if not node:
        return prev
    n = node.next
    node.next = prev
    return self._reverse(n, node)