https://leetcode.com/problems/rotate-list/description/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
맨 오른쪽 끝 원소를 맨 앞으로 보내 rotate 시키는 작업을 k번 한 결과물을 리턴하는 문제다.
naive하게 풀면 당연히 O(NK) 시간이 걸리는데 N은 최대 500이니까 어찌어찌 한다 쳐도 k가 최대 20억이기 때문에
time complexity가 절대 K에 비례하면 안된다.
즉 K가 N보다 클 수 있다는 건데 이 경우는 한가지를 명심해야 한다.
N개의 원소를 rotate 시켰을때 처음 리스트랑 똑같아진다는 점을 이용해야한다.
잘 생각해보면 K % N 번만 rotate 시키면 된다는걸 알수있다.
그리고 엣지 케이스도 잘 생각하자.
1. N = 0
2. K = 0
3. N = K
처음엔 이렇게 구현했는데 two pointers를 이용해서 원패스로 구현하려고 하다보니 코드가 많이 지저분해지고 예외처리 로직도 많이 들어간거같다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not k:
return head
dummy = ListNode(0, head)
kth, moved = self.findKthAndLength(dummy, k)
if not kth: #
k %= moved - 1 # moved - 1 = listlen
kth, _ = self.findKthAndLength(dummy, k)
if not kth.next or not k:
return head
newtail, rightend = dummy, kth # 'newtail' will be (k+1)th node from right side
while rightend.next:
rightend = rightend.next
newtail = newtail.next
newhead = newtail.next
newtail.next = None # make it tail!
rightend.next = dummy.next
return newhead
def findKthAndLength(self, head, k):
moved = 0
p = head
while p and moved < k:
p = p.next
moved += 1
return (p, moved)head를 변경할 일이 없는데 굳이 dummy를 쓸필요 없었던거같고
findKth 하고나서 if문을 떡칠할바에 그냥 length 함수를 구현해서 twopass로 가면 훨씬 실수할 여지가 적고 깔끔했을거같다.
아니면 처음부터 Constraints를 보고 엣지케이스부터 꼼꼼히 따지고 다 처리하고 시작하던가.
이번문제에서는 내가 부족한 부분을 많이 발견할 수 있었다. 실제 인터뷰에서 이렇게 풀면 안될것이다.
다시 구현해봐야겠다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
"""
special cases
1. N = 0
2. K = 0
3. N % K = 0
"""
if not head or not k:
return head
length = self.length(head)
k %= length
if not k:
return head
dummy = ListNode(0, head)
kth = self.findKth(dummy, k)
# find newtail (tail after rotation) and curtail (current last node)
newtail, curtail = dummy, kth
while curtail.next:
curtail = curtail.next
newtail = newtail.next
# rotate
newhead = newtail.next
newtail.next = None # make it tail node!
curtail.next = head # connect current tail to current head
return newhead
def length(self, head):
count = 0
p = head
while p:
count += 1
p = p.next
return count
def findKth(self, head, k):
p = head
for i in range(k):
p = p.next # does not need to null-check because k < length already (look at line 17~21)
return p여전히 엣지케이스는 처리해야되고 더미노드를 쓰는게 편하다.
이 문제 자체가 원래 엣지케이스가 좀 까다로운 문제인듯하다.
그래도 length 함수를 따로 도입해서 two pass로 푸니까 실수 확률이 훨씬 적어졌다.