솔루션: 목록 끝에서 N번째 노드 제거

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #19(중간): 목록 끝에서 N번째 노드 제거

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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

Follow up: Could you do this in one pass?

예:

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

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

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

제약:

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

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

단일 연결 목록을 사용하여 목록의 끝을 찾는 유일한 방법, 따라서 끝에서 n번째 노드는 실제로 끝까지 반복하는 것입니다. 여기서 문제는 한 번에 해결 방법을 찾으려고 시도하는 것입니다. 순진한 접근 방식은 배열의 각 노드에 대한 포인터를 저장하여 끝에 도달하면 끝에서 n 번째를 계산할 수 있지만 O(M) 추가 공간이 필요합니다. 여기서 M은 길이입니다. 연결 목록.

약간 덜 순진한 접근 방식은 배열에 마지막 n+1 노드 포인터만 저장하는 것입니다. 이는 목록을 반복하면서 스토리지 배열의 요소를 순환 방식으로 덮어쓰면 달성할 수 있습니다. 이렇게 하면 공간 복잡도가 O(N+1)로 낮아집니다.

단 한 번의 패스와 O(1) 추가 공간으로 이 문제를 해결하려면 하나의 포인터로 목록의 끝에 도달하는 동시에 끝에서 n번째 노드에 도달하는 방법을 찾아야 합니다. 두 번째 포인터로.

이를 위해 우리는 두 번째 포인터(느림)를 시작하기 전에 첫 번째 포인터(빠름)를 먼저 시작하여 두 포인터를 n 노드만큼 시차를 둘 수 있습니다. 이렇게 하면 fast가 끝에 도달하는 동시에 slow가 끝에서 n번째 노드에 도달하게 됩니다.



대상 노드를 제거하려면 대상 노드보다 먼저 노드에 액세스해야 하므로 종료 조건으로 fast == null 대신 fast.next == null을 사용하여 한 노드를 더 일찍 중지할 수 있습니다.

이것은 불행하게도 n이 리스트의 길이와 같을 때 문제를 일으키고, 첫 번째 노드를 대상 노드로 만들어서 대상 노드 이전의 노드를 찾을 수 없게 만듭니다. 그러나 이 경우 대상 노드의 양면을 함께 연결할 필요 없이 head.next를 반환할 수 있습니다.

그렇지 않으면 목표 앞의 노드를 성공적으로 찾으면 목표 뒤의 노드와 함께 연결한 다음 헤드를 반환할 수 있습니다.

구현:

네 가지 언어 모두의 코드 간에는 약간의 차이만 있습니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var removeNthFromEnd = function(head, n) {
    let fast = head, slow = head
    for (let i = 0; i < n; i++) fast = fast.next
    if (!fast) return head.next
    while (fast.next) fast = fast.next, slow = slow.next
    slow.next = slow.next.next
    return head
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast, slow = head, head
        for _ in range(n): fast = fast.next
        if not fast: return head.next
        while fast.next: fast, slow = fast.next, slow.next
        slow.next = slow.next.next
        return head

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        for (int i = 0; i < n; i++) fast = fast.next;
        if (fast == null) return head.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head, *slow = head;
        for (int i = 0; i < n; i++) fast = fast->next;
        if (!fast) return head->next;
        while (fast->next) fast = fast->next, slow = slow->next;
        slow->next = slow->next->next;
        return head;
    }
};