๋ฐ์ํ
๋ฌธ์ ๋งํฌ : https://leetcode.com/problems/reverse-linked-list/
Reverse Linked List - LeetCode
Can you solve this real interview question? Reverse Linked List - Given the head of a singly linked list, reverse the list, and return the reversed list. Example 1: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg] Input: head = [1,2,3,4,5] O
leetcode.com
ํ์ด
# 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
๋ฐ์ํ