문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
링크드 리스트 뒤에서 N번째 노드를 지워라
예제
input: 1 -> 2 -> 3 -> 4 -> 5 -> null, n = 2
output: 1 -> 2 -> 3 -> 5 -> null
풀이
2 포인터 문제. 두 포인터 사이에 n 만큼의 갭을 만든다. 첫 번째 포인터가 끝에 다다르면 두 번째 포인터.next에 위치해 있는 노드가 뒤에서 n 번째의 노드가 된다.
여러 코너 케이스를 피하기 위해 dummy 노드를 만들고 dummy.next = head로 설정 후 dummy 노드부터 시작한다. 안 그러면 input이 1 -> null, n = 1 처럼 몇 가지 케이스들에 맞는 컨디션들을 따로 만들어야 할 수도 있기 때문이다.
dummy 노드로 시작하는 것이 다수 링크드 리스트 문제에 여러 코너 케이스를 쉽게 해결하게 해 준다고 하니 기억하자.
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode();
dummy.next = head;
// 더미 노드로부터 출발
ListNode p1 = dummy;
ListNode p2 = dummy;
// p1과 p2 사이에 n 만큼의 갭을 생성
for (int i=0; i<n+1; i++) {
p1 = p1.next;
}
// p1이 마지막에 다다를 때까지 움직인다
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
// 현재 p1 은 null이고 p2의 다음 노드가 삭제할 대상이다
// 고로 p2의 다음은 p2의 다음의 다음으로 설정한다
p2.next = p2.next.next;
// dummy.next가 실질적인 head를 가리키고 있기 때문에 head 대신 dummy.next를 반환하는 것을 기억하자
return dummy.next;
}
Complexity
time: O(n) - n 노드 갯수 만큼 loop을 돈다.
space: O(1) - 몇개 안되는 변수를 생성하였다.