Постановка задачи

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Пример 1:

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

Пример 2:

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

Пример 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

Объяснение

Одиночный указатель

Один из подходов к решению этой проблемы - использовать единый указатель, выполнив следующие шаги.

  • Расчет длины связанного списка
  • Вычтите n из длины
  • Начните с головы и перейдите к вышестоящему (length-n) узлу.

Фрагмент кода C ++ для вышеуказанного решения выглядит следующим образом:

ListNode* first = head;

while (first != null) {
    length++;
    first = first.next;
}

length -= n;
first = dummy;

while (length > 0) {
    length--;
    first = first.next;
}

first.next = first.next.next;

// dummy next is pointing to the head of the list.
return dummy.next;

Вышеупомянутое решение подходит, но основная проблема заключается в повторении итераций в связанном списке.

Рассмотрим случай, когда список очень большой и имеет длину 1000000, и нам нужно удалить пятый узел из последнего. При использовании вышеупомянутого подхода мы дважды перебираем список.

Два указателя

Мы можем использовать два указателя и удалить узел из списка за один проход. Давайте проверим алгоритм этого.

Алгоритм

- Initialize two pointers slow and fast pointing to the head of the list.

- Loop while n > 0
  - fast = fast->next
  - decrement n--

// if fast is nil it means the first node is supposed to be removed
- if fast == nil
  - head = head->next
  - return head

- Loop while fast->next != nil
  - slow = slow->next
  - fast = fast->next

- if slow->next != nil && slow->next->next
  - slow->next = slow->next->next
- else
  - slow->next = nil
- end

return head

Решение C ++

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast;
        ListNode* slow;

        fast = head;
        slow = head;

        while(n){
            fast = fast->next;
            n--;
        }

        if(fast == NULL){
            head = head->next;
            return head;
        }

        while(fast->next){
            slow = slow->next;
            fast = fast->next;
        }

        if(slow->next && slow->next->next){
            slow->next = slow->next->next;
        } else {
            slow->next = NULL;
        }

        return head;
    }
};

Решение Golang

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

	slow, fast := node, node

	for ; n > 0; n-- {
		fast = fast.Next
	}

	for ; fast.Next != nil; slow, fast = slow.Next, fast.Next {}

	slow.Next = slow.Next.Next

	return node.Next
}

Решение Javascript

var removeNthFromEnd = function(head, n) {
    let fast = head;
    let slow = head;

    while(n > 0) {
        fast = fast.next;
        n--;
    }

    if(fast === null) return head.next;

    while(fast.next !== null) {
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;

    return head;
};

Давайте проверим наш алгоритм.

head = [1, 2, 3, 4, 5]
n = 2

Step 1: fast = head, slow = head

        slow, fast -- [1, 2, 3, 4, 5]

Step 2: Loop while n > 0
        2 > 0 = true

        fast = fast->next

                   fast
                    |
        slow -- [1, 2, 3, 4, 5]

        n--
        n = 1

Step 3: Loop while n > 0
        1 > 0 = true

        fast = fast->next

                      fast
                       |
        slow -- [1, 2, 3, 4, 5]

        n--
        n = 0

Step 4: Loop while n > 0
        0 > 0 = false

Step 5: if fast == nil
        = false

Step 6: Loop while fast.next != nil
        = true
        // fast.next pointing to node 4 address

        slow = slow.next
        fast = fast.next

           slow  fast
            |     |
        [1, 2, 3, 4, 5]

Step 7: Loop while fast.next != nil
        = true
        // fast.next pointing to node 5 address

        slow = slow.next
        fast = fast.next

             slow  fast
               |     |
        [1, 2, 3, 4, 5]

Step 8: while fast.next != nil
        = false

Step 9: if slow.next && slow.next.next
        slow is node 3
        slow.next is node 4
        slow.next is node 5

        slow.next = slow.next.next
        // so node 3 next is now pointing to 5

Step 10: return head

         [1, 2, 3, 5]

Первоначально опубликовано на https://alkeshghorpade.me.