Split Linked List In Parts
링크드 리스트 노드 head 와 정수 k 가 주어질 때 리스트를 k 개의 연속적인 부분
리스트로 잘라서 k 개의 노드 리스트로 반환하는 문제이다.
이 문제는 힌트를 보고 풀었는데, 리스트의 길이를 N 이라고 하면 각각의 파트는 N/k
개의 원소를 가지며 N%k 개 만큼은 이거보다 하나를 더 가지게 된다.
def splitListToParts(head, k) -> List[Optional[ListNode]]:
def length(node):
n = 0
while node:
n += 1
node = node.next
return n
N = length(head)
window = N // k
plus = N % k
sentinel = ListNode(next=head)
prev, cur = sentinel, head
nodes = [None] * k
for i in range(k):
nodes[i] = cur
w = window
while w and cur:
prev, cur = cur, cur.next
w -= 1
if i < plus and prev and cur:
prev, cur = cur, cur.next
if prev:
prev.next = None
return nodes
- 역시 센티넬 노드를 활용한다. 센티넬 노드가 있으면 항상
prev노드가 valid한 노드를 가리킬 수 있어서 유용하다. cur노드로 전체를 훑는게 아니라,range(k)만큼 파트를 만든다고 생각한다. 그리고 각i에 대해서window크기 만큼 노드를 진행시켜서prev노드가 유효한 경우에만 이걸 끊어버린다.