[LeetCode] 19. Remove Nth Node From End of List - Java

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

Remove Nth Node From End of List - LeetCode

---

문제

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

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

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Follow up: Could you do this in one pass?

---

풀이

풀이 과정

연결 리스트와 정수 n이 주어졌을 때 뒤에서 n번째 노드를 제거한 연결 리스트를 구해야한다.

두 개의 포인터를 이용해 뒤에서 n번째 위치를 찾아낸다.
첫 번째 포인터는 처음 위치부터 시작하는 포인터, 두 번째 포인터는 첫 번째 포인터로부터 n만큼 떨어진 위치부터 시작하는 포인터이다.
n만큼 떨어진 위치부터 시작한 포인터가 리스트의 끝에 도달하게 되었을 때 첫 번째 위치부터 시작한 포인터는 뒤에서 n만큼 떨어진 위치에 도달하게 되므로 해당 위치의 노드를 제거한다.

우선 최종적으로 반환할 리스트를 하나 선언한다.

// 최종적으로 반환할 ListNode 선언
ListNode answer = new ListNode(0);
answer.next = head;

 

처음 위치부터 시작할 포인터와 n만큼 떨어진 위치부터 시작할 포인터 두 개를 선언한다.

// 처음 위치부터 시작할 포인터
ListNode slow = answer;
// n만큼 떨어진 위치부터 시작할 포인터
ListNode fast = answer;

for(int i = 0; i < n; i++){
    fast = fast.next;
}

 

n만큼 떨어진 위치에서 시작한 포인터가 끝에 도달할 때까지 두 포인터를 모두 이동한다.

// n만큼 떨어져서 시작한 포인터가 끝에 도달할 때까지 두 포인터 이동
while(fast.next != null){
    slow = slow.next;
    fast = fast.next;
}

 

fast 포인터가 리스트의 끝에 도달하였을 때 slow의 next를 그 다음 노드로 교체한다.

// 두 포인터가 n만큼 떨어져서 움직였으므로
// fast가 끝에 도달하면 slow는 뒤에서 n만큼 떨어진 자리에 위치하게 됨
// slow의 next를 next.next로 설정
slow.next = slow.next.next;

 

answer 리스트를 반환한다. 이 때 첫 번째 노드를 임의로 설정하고 그 다음 노드에 head를 세팅하였으므로 최종적으로 반환하는 값은 answer.next이다.

// answer 첫번째 노드를 0으로 임의 설정하고 다음 노드에 head를 넣었으므로
// answer.next를 반환
return answer.next;

---

최종 코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 최종적으로 반환할 ListNode 선언
        ListNode answer = new ListNode(0);
        answer.next = head;

        // 처음 위치부터 시작할 포인터
        ListNode slow = answer;
        // n만큼 떨어진 위치부터 시작할 포인터
        ListNode fast = answer;

        for(int i = 0; i < n; i++){
            fast = fast.next;
        }

        // n만큼 떨어져서 시작한 포인터가 끝에 도달할 때까지 두 포인터 이동
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }

        // 두 포인터가 n만큼 떨어져서 움직였으므로
        // fast가 끝에 도달하면 slow는 뒤에서 n만큼 떨어진 자리에 위치하게 됨
        // slow의 next를 next.next로 설정
        slow.next = slow.next.next;

        // answer 첫번째 노드를 0으로 임의 설정하고 다음 노드에 head를 넣었으므로
        // answer.next를 반환
        return answer.next;
    }
}

---