Удалить N-й узел из конца данного связанного списка  


Сложный уровень средний
Часто спрашивают в саман Амазонка Арцезиум Набор фактов Постигать интуитивно Zoho
Связанный список

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

Задача «Удалить N-й узел из конца данного связанного списка» утверждает, что вам дан связанный список с некоторыми узлами. И теперь вам нужно удалить n-й узел из конца связанного списка.

Пример  

Удалить N-й узел из конца данного связанного спискашпилька

2->3->4->5->6->7
delete 3rd node from last
2->3->4->6->7

Объяснение: 2-й узел с конца - 6., поэтому мы его удалим. И после удаления узла у нас остается связанный список, показанный на выходе.

Подход  

Связанный список - это линейная структура данных, использующая указатели. И это избавляет нас от больших вычислительных затрат при добавлении массива дополнительных элементов. Теперь проблема в том, чтобы удалить n-й узел из связанного списка. Здесь я должен сказать вам, что вам не указано количество узлов в связанном списке. Итак, какой подход выбрать для решения проблемы? Когда нам нужно удалить n-й узел из конца связанного списка.

Наивный подход

Наивный подход будет заключаться в том, чтобы сначала вычислить или вычислить длину связанного списка. Этот способ требует, чтобы мы сначала запустили цикл до конца связанного списка. Но как расчет связанного списка поможет в удалении n-го узла с конца? Для решения проблемы сначала рассчитаем длину связанного списка. Затем мы вычтем данный ввод из длины. Теперь просто удалить узел на длине-n расстоянии от головы.

Смотрите также
Клонирование графа

Оптимизированный подход

Оптимизированный подход будет без расчета размера связанного списка. Есть уловка, чтобы решить эту проблему. Сначала мы проходим узел, который был инициализирован как головной, до n-го узла с самого начала. Теперь мы находимся в узле, который находится на расстоянии n от начального узла (головы). Затем мы инициализируем новую переменную, равную head. Затем начните обход обоих узлов, пока первый узел не достигнет последнего узла связанного списка. В это время наша вторая переменная будет в n + 1-м узле с конца. Теперь вам просто нужно удалить следующий узел.

Код:  

Код C ++ для удаления N-го узла из конца данного связанного списка

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node* next;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

node* deleteNthNodeFromLast(node* head, int n){
    // first move ahead n nodes
    // then start traversing from the start until the end node
    // delete the temporary node
    node* cur = head;
    while(n--){
        cur = cur->next;
        if(!cur){
            cur = head;
            head = head->next;
            free(cur);
            return head;
        }
    }
    node* tmp = head;
    while(cur->next){
        tmp = tmp->next;
        cur = cur->next;
    }
    cur = tmp->next;
    tmp->next = tmp->next->next;
    return head;
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  head = deleteNthNodeFromLast(head, 3);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}
Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 4 6 7

Код Java для удаления N-го узла из конца данного связанного списка

import java.util.*;
class node{
    int data;
    node next;
}

class Main{
    static node create(int data){
        node tmp = new node();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static node deleteNthNodeFromLast(node head, int n){
        // first move ahead n nodes
        // then start traversing from the start until the end node
        // delete the temporary node
        node cur = head;
        while(n-- > 0){
            cur = cur.next;
            if(cur == null){
                cur = head;
                head = head.next;
                return head;
            }
        }
        node tmp = head;
        while(cur.next != null){
            tmp = tmp.next;
            cur = cur.next;
        }
        cur = tmp.next;
        tmp.next = tmp.next.next;
        return head;
    }

    public static void main(String[] args){
        // create a linked list
        node head = new node();
        head = create(2);
        head.next = create(3);
        head.next.next = create(4);
        head.next.next.next = create(5);
        head.next.next.next.next = create(6);
        head.next.next.next.next.next = create(7);

        System.out.print("Old Linked List: ");
        node tmp = head;
        while(tmp != null){
            System.out.print(tmp.data+" ");
            tmp = tmp.next;
        }
        head = deleteNthNodeFromLast(head, 3);

        System.out.print("\n"+"New Linked List: ");
        tmp = head;
        while(tmp!=null){
            System.out.print(tmp.data+" ");
            tmp = tmp.next;
        }
    }
}
Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 4 6 7

Анализ сложности  

Сложность времени

НА), потому что мы прошли через весь связанный список, что будет стоить нам линейной временной сложности.

Смотрите также
Обратные узлы в K-Group

Космическая сложность

О (1), поскольку мы только что сохранили некоторые постоянные переменные, требуемая пространственная сложность остается постоянной.