LeetCode 19(Remove Nth Node From End of List, Python)

1. 문제 링크

• https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

2. 문제 설명

• 연결 리스트(Linked List)와 n이 주어졌을 때, 마지막에서 n번째 노드를 삭제하기
• 예시) head = [1,2,3,4,5], n = 2 가 주어지면 끝에서 2번째인 노드를 삭제하여 [1,2,3,5]을 반환

3. 처음 풀이

• 주어진 head를 노드 하나씩 갈 때마다 sz = 0을 1씩 증가시켜서 전체 개수를 세어 삭제할 위치를 계산함
• 이후 새로운 연결 리스트를 생성한 후 주어진 노드를 하나씩 연결시켜 주고, 삭제할 위치에서는 하나 생략하고 그다음 노드를 연결

# 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]:
        # 노드의 개수 세기
        num = head
        sz = 0
        while num:
            sz += 1
            num = num.next
        
        # 삭제할 노드의 위치 계산
        target = sz - n

        # 새로운 연결 리스트 생성
        new = ListNode(0)
        cur = new
        
        # 삭제할 노드 이전까지 새로운 리스트에 노드 추가
        while target:
            cur.next = head
            head = head.next
            cur = cur.next
            target -= 1

        # 삭제할 노드를 건너뛰고 새로운 리스트에 연결
        cur.next = head.next

        return new.next

4. 다른 풀이

• 끝에서 n번째를 알려면 fast를 미리 n번 가게 해두고
• fast와 slow를 동시에 한칸씩 가다가 fast가 도착하면 slow가 끝에서 n번째에 있음을 이용

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 초기화: 두 개의 포인터를 머리 노드로 설정
        fast, slow = head, head
        
        # 먼저 fast 포인터를 n번째로 이동
        for _ in range(n): 
            fast = fast.next
        
        # 만약 fast가 끝에 도달했다면 n이 전체 길이이므로 첫 번째 노드를 삭제해야 함
        if not fast: 
            return head.next
        
        # fast와 slow 포인터를 함께 이동하여 fast가 끝에 도달하면 slow는 끝에서 n번째에 도달
        while fast.next: 
            fast, slow = fast.next, slow.next
        
        # n번째 노드 삭제
        slow.next = slow.next.next
        
        # 변경된 연결 리스트의 헤드 반환
        return head

5. 배운 점

• 아직 연결 리스트가 헷갈린다.
• 내 풀이에서 cur = head로 놓고 cur를 변경했을 때 head에 변경이 반영 안 되는 것 같아서 새로 연결 리스트를 생성했는데
• 다른 풀이에서 slow = head로 놓고 slow를 변경하니 head가 변경이 되었다.
• 아직 변수에 대한 이해가 모자란지 연결 리스트를 다루는 방법이 어렵다. 언제는 이름표만 바뀌고 언제는 연결이 변경이 되는 거지..?