뒤에서 n번째 노드 삭제하기

 

알고리즘

1. 포인터 hare를 n만큼 먼저 이동시킨다.

2. curr와 hare를 같은 속도로 이동시킨다. 이때 curr는 헤드에서 hare는 n번째 노드에서 출발한다.

3. curr과 hare사이에는 n개의 노드가 있으므로,
   hare가 뒤에서부터 1번째에 있을 때 curr는 뒤에서부터 n+1번째 노드에 있다.
   그러므로 curr.next가 다음다음 노드를 가르키도록 수정하여 n번째 노드를 삭제할 수 있다.

엣지 케이스

• n이 연결리스트의 길이와 같을때가 엣지케이스이다.
• curr의 다음 노드를 삭제하는 것이 아니라, 리스트의 첫번째 노드를 삭제해야해야한다.
• 길이가 n인 연결리스트의 헤드에서 n번 떨어진 곳은 null이다.
• 그러므로 hare가 null값인지에 따라 이를 구분할 수 있다.

복잡도 분석

• 시간복잡도: O(N)
• 공간복잡도: O(1)