[leetcode][Easy][LinkedList] 206. Reverse Linked List 풀이, 해설

문제링크 : https://leetcode.com/problems/reverse-linked-list/

Reverse Linked List - LeetCode

 

 

풀이

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        stack = [] 
        prev = None
        while head != None:
            data = ListNode()
            data.val = head.val
            data.next = prev
            
            stack.append(data)
            
            prev = data
            head = head.next
            
        if stack:
            return stack.pop()
    
        return head

 

 

해설

- two pointer 방법 이용 

# time complexity o(n), memory complexity o(1)
prev, cur = None, head 

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

return prev

 

- 재귀 recursive

  # time complexity o(n), memory complexity o(n)
if not head:
    return None

newHead = head 
if head.next:
    newHead = self.reverseList(head.next)
    head.next.next = head
head.next = None

return newHead