log 2022-04-11

---

• sport
  • leet - Remove Nth Node From End of List

sport

leet - Remove Nth Node From End of List

• 아이디어
  • 두 포인터 간 거리를 n으로 유지하면서 오른쪽 포인터를 끝으로 옮기면,
  • 왼쪽 포인터가 가리키는 노드가 삭제할 노드가 된다.
  • 만약 오른쪽 포인터를 끝으로 옮기다가 거리가 n 되기 전에 끝에 도달했다면, 그건 head가 삭제할 노드라는 뜻이다.
• 시간복잡도 O(n)

아이디어는 같은데, 엣지케이스 (끝/head)처리 귀찮아서 대충하다가 5번 틀림. (3RE, 2WA) 엣지케이스에 대해 곰곰히 생각 후 마지막 항목을 생각해냈고, 다시 짜보니 5분만에 풀림..

py solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if not head.next:
            return None
        
        first = head
        second = head
        cnt = n
        
        while cnt > 0:
            if not second.next:
                return head.next
            second = second.next
            cnt -= 1
        
        while second.next:
            first = first.next
            second = second.next
        
        first.next = first.next.next
        return head

• 다른 사람 풀이
  • 대부분 원리는 같음
  • head 앞에 더미 노드를 추가해서 구현을 간단하게 함.
  • (slow가 head더라도, head_dummy.next가 head를 )
  • 시간복잡도 O(n)

py solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        head_dummy = ListNode()
        head_dummy.next = head

        slow, fast = head_dummy, head_dummy
        for _ in range(n): 
            fast = fast.next

        while(fast.next!=None):
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return head_dummy.next

---