[LeetCode] 19. Remove Nth Node From End of List

 

19. Remove Nth Node From End of List

Medium

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Follow up: Could you do this in one pass?

---

문제 풀이

• 단방향 링크드 리스트가 주어진다.
• 뒤에서부터 n 만큼 떨어진 노드를 제거해야한다.
• 문제에서 탐색을 한번만 진행하여 풀 수 있는지 에 대한 Follow Up 이 있다.

Two pass

1. 더미 노드를 생성해서 해드 노드 이전 노드로 설정한다.
2. 링크드리스트의 총길이를 구한다.
3. 총길이에서 n 만큼을 빼고, 뺀 길이만큼 더미에서 하나씩 옮겨준다.
4. 더미에서 시작했기 때문에 next.next 를 참조해도 참조 에러가 나지 않을 것이다.
5. 총 길이에서 뒤에서 n 만큼 떨어진 값을 빼주었기 때문에, 그 값만큼 이동시키면 제거하고자 하는 노드의 이전 노드까지 이동한다.
6. 그 노드를 next.next 노드로 연결해준다.

One pass

1. 더미 노드를 생성하고 두개의 시작 노드를 생성한다.
2. n 만큼 첫번째 시작 노드를 이동시킨다.
3. 첫번째 시작노드가 종료될 때까지 첫번째 시작 노드와 두번째 시작 노드를 하나씩 옮겨준다.
4. Two pass 와 마찬가지로 더미부터 시작하여 전체 길이에서 n 을 뺀 만큼 두번째 시작 노드를 옮기기 때문에,
5. 마지막에 선택 되는 노드는 삭제할 노드 이전 노드이다. 

 

소스 코드

Two pass

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        dummy = ListNode(0)
        dummy.next = head
        cnt = head
        while cnt:
            length += 1
            cnt = cnt.next
        length -= n
        temp = dummy
        for i in range(length):
            temp = temp.next
        temp.next = temp.next.next
        return dummy.next

One pass

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy
        for i in range(0, n + 1):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next