LeetCode (1) - Remove Nth Node From End of List (파이썬, python)

❓ 문제

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?

---

Given Code

# 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: ListNode, n: int) -> ListNode:
        

---

Linked List

문제에서 class ListNode로 주어진 자료구조는 Linked List(연결 리스트)로, 각 노드가 값(val)과 다음 노드의 위치를 가리키는 형식입니다. ListNode는 self.val로 값을, next로 다음 객체를 표현하고 있어요.

이때까지 in/out을 직접 처리해야했던 백준이나 함수를 만들어주면 되는 프로그래머스와 달리 input인 ListNode가 어떤 식으로 들어올지 바로 이해가 안됐는데 몇 번 print해보고 알게됐어요! Run했을 때 stdout 표시를 지원하는 LeetCode인 만큼 잘 활용하면 편리할 것 같습니다!

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        while head != None:
            # print(head.val)
            head = head.next

기본적으로 이런식으로 head값을 차례로 불러올 수 있습니다.

---

접근법

뒤에서 n번째인 경우를 제외한 ListNode객체를 return해주면 되는 간단한 문제라 5분이면 될 줄 알았는데 ListNode class가 mutable하다는 아이디어가 없어서 조금 해맸습니다.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        lead = head
        follow = head
        
        for i in range(n):
            lead = lead.next
        
        while(lead.next != None):
            lead = lead.next
            follow = follow.next
        follow.next = follow.next.next
        
        return head

lead와 follow를 두어서 follow를 뒤에서 n번째인 위치로 이동시켜 그때의 연결을 다음 ListNode로 연결하려고 했는데 에러가 났습니다. 에러가 난 케이스는 edge인 상황인데 이럴 때 앞쪽에 더미값을 주는 방법으로 해결할 수 있습니다. 수정한 코드입니다.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(val = 0, next = head)
        lead = dummy
        follow = dummy
        
        for i in range(n):
            lead = lead.next
        
        while(lead.next != None):
            lead = lead.next
            follow = follow.next
        follow.next = follow.next.next
        
        return dummy.next

head 맨 앞에 0을 추가한 dummy linked list를 만들어 edge상황에서의 에러를 회피했습니다.