34. Remove Nth Node From End of List

문제

연결리스트의 끝에서 n번째 노드를 삭제하고 연결리스트의 head를 반환하라.

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

 

내가 생각한 방식

1) slow 포인터가 fast 포인터보다 n칸 뒤에 있게 설정. 

2) slow, fast를 한 칸씩 이동.

3) fast가 연결 리스트의 끝을 가리키면 traverse 중단.

    slow는 삭제할 노드의 한 칸 뒤를 가리키게 됨.

4) 삭제 실행 : slow.next가 다음 노드의 다음 노드를 가리키게 함.

 

문제점 : [1,2], n = 2인 경우 fast가 None을 가리킴.

=> 1을 삭제해야 하는데 2를 삭제함.

def removeNthFromEnd(head, n):
    slow = head
    fast = head

    for _ in range(n):
        fast = fast.next
	
    # [1,2], n = 2인 경우 fast가 None이 됨
    while fast and fast.next:
        fast = fast.next
        slow = slow.next

    if slow.next:
        slow.next = slow.next.next

    else:
        return None

    return head

 

해결 방식

https://redquark.org/leetcode/0019-remove-nth-node/

def removeNthFromEnd(head, n):
    slow = head
    fast = head

    for i in range(n):
        # fast의 다음칸이 없는데 i가 n-1과 같다는 것은
        # 첫번째 노드를 지우라는 뜻
        # head가 next 가리키게 한 다음 head 반환
        if not fast.next:
            if i == n - 1:
                head = head.next
            	return head
        fast = fast.next

    while fast.next:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return head