#19. Remove Nth Node From End of List

단순하게 풀면 주어진 문제의 경우 단방향 링크드 리스트이므로

1. 전체의 길이를 체크
2. 원하는 위치의 노드를 제거

위와 같이 단순하게 풀 수 있다. 하지만 위의 경우 링크드 리스트를 2번 순회해야 한다는 문제점이 있다.

이를 한 번 순회하는 것으로 해결할 수 있는데,

1. back, front 2개의 포인터를 만든다.
2. front를 n만큼 이동시킨다. (front와 back의 거리를 n만큼 둔다.)
3. 그 뒤, front와 back을 동시에 하나씩 front가 맨 마지막에 도달할 때까지 이동시킨다.
4. back을 이용해서 노드를 제거한다.

더 나아가, 맨 앞에 dummy노드를 만들고 이 dummy노드를 head 이전에 놓으면 edge case에 있는 지저분한 작업들을 깔끔하게 해결할 수 있게 된다.

type ListNode struct {
	Val int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}

	back, front := dummy, dummy
	for i := 0; i < n; i++ {
		front = front.Next
	}

	for front.Next != nil {
		front = front.Next
		back = back.Next
	}

	back.Next = back.Next.Next
	return dummy.Next
}