๊ฐ๋ฐ/๐ค ์๊ณ ๋ฆฌ์ฆ
[leetcode][Easy][LinkedList] 206. Reverse Linked List ํ์ด, ํด์ค
ttoance
2023. 12. 19. 02:43
๋ฌธ์ ๋งํฌ : https://leetcode.com/problems/reverse-linked-list/
ํ์ด
# 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
๋ฐ์ํ