(Leetcode) 206 - Reverse Linked List
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/reverse-linked-list/
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]:
reversed = None
stack = []
current = head
while current is not None:
stack.append(current)
current = current.next
if len(stack) == 0:
return None
reversed = stack.pop()
current = reversed
while stack and stack[-1] is not None:
current.next = stack.pop()
current = current.next
current.next = None
return reversed
객체 값 비교하기
참고한 글 : Compare object instances for equality by their attributes
example1 = Solution()
example_result1 = example1.reverseList(ListNode(val=1, next=ListNode(
val=2, next=ListNode(val=3, next=ListNode(val=4, next=ListNode(val=5))))))
assert example_result1 == ListNode(val=5, next=ListNode(
val=4, next=ListNode(val=3, next=ListNode(val=2, next=ListNode(val=1)))))
객체간의 비교라서 이렇게 작성하면 테스트에 실패하게 된다.
방법1 __eq__ 구현
정석적인 방법이지만 번거로워서 이 방법은 스킵했다.
방법2 pickle 사용해서 구현
import pickle
assert pickle.dumps(example_result1) == pickle.dumps(ListNode(val=5, next=ListNode(
val=4, next=ListNode(val=3, next=ListNode(val=2, next=ListNode(val=1))))))
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
다른 풀이 (24.05.01)
다시 풀 기회가 생겨서 이번에는 자바로 풀어보았다. 비슷한 문제에서 2개의 포인터를 이용해서 풀이하는 것을 봤었어서 이 문제에 적용해보았다.
public ListNode reverseList(ListNode head) {
if(head == null) {
return null;
}
ListNode p1 = head;
ListNode p2 = head.next;
p1.next = null;
while (p2 != null) {
ListNode temp = p2.next;
p2.next = p1;
p1 = p2;
p2 = temp;
}
return p1;
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다. 첫 풀이와 달리 추가적인 공간이 사용되지 않았다는 부분이 좋은 부분이라 생각된다.