leetcode : Remove Nth Node From End of List
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
Remove Nth Node From End of List - LeetCode
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
Linked List와 n이 주어질 때 리스트의 끝에서 n번째 (앞에서 n번째가 아님) 노드를 원스캔으로 제거하라는 문제다.
그닥 어렵지 않다. n정도 길이의 큐에 노드를 계속 넣어주자. 그럼 순회가 끝났을 때 끝에서 n번째 노드도 큐에 들어있을것 아닌가? 끝에서 n번째 노드를 제거하려면 끝에서 n+1번째 노드, 즉 previous 노드가 있어야 되니까 큐의 길이는 n+1로 유지하면 된다.
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
q = []
node = head
while node:
q.append(node)
node = node.next
if len(q) == n + 2:
q.popleft()
if len(q) == n:
return head.next
q[0].next = q[1].next
return head
근데 이게 보기 좀 복잡하면 그냥 리스트 길이를 n+1로 유지하지 않아도 된다.
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
q = []
node = head
while node:
q.append(node)
node = node.next
if len(q) == n:
return head.next
q[-n-1].next = q[-n].next
return head
자 근데 생각해보자. n+1길이의 리스트에 노드를 막 집어넣었는데.. 그중에 우리가 필요한건 딱 2개 아닌가? 그럼 나머지 노드들은 큐에 있을 필요가 있을까?
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
prev = head
node = head
i = 0
while i < n:
node = node.next
i += 1
if not node:
return head.next
node = node.next
while node:
prev = prev.next
node = node.next
prev.next = prev.next.next
return head
거리를 n+1만큼 벌려놓는게 핵심이다. n칸 움직였는데 node가 None이 됐으면 총 노드 수가 n개있는거니까 head노드가 제거돼야한다. 그래서 head.next를 리턴한다. node가 None이 아니면 node = node.next를 해서 거리를 n+1로 벌려놓고 끝까지 가면 된다. node가 None이 될때까지 갔으면 prev는 끝에서 n번째 요소의 바로 이전 노드를 가리키고 있을거다. 그래서 prev.next = prev.next.next로 n번째 노드를 제거한다.