從沒有頭指針的鍊錶中刪除節點


難度級別 容易獎學金
經常問 GE醫療集團 空氣質量
鍊錶 技術編劇

問題陳述

問題“在沒有頭指針的情況下從鏈接列表中刪除節點”指出您的鏈接列表中包含一些節點。 現在,您要刪除一個節點,但沒有其父節點地址。 因此,刪除該節點。

從沒有頭指針的鍊錶中刪除節點

2->3->4->5->6->7
Node to be deleted: 4
2->3->5->6->7

說明:由於我們要刪除值為4的節點,因此從鏈接列表中將其刪除,並保留了輸出中提到的列表。

無頭指針刪除節點的方法

鍊錶是一種線性數據結構,與數組相比,它具有很大的優勢,因為它的大小可以變化。 如果要在鏈接列表中添加元素,則可以在O(1)時間添加它。 考慮到您首先要插入元素。 但是,如果必須在普通數組中執行相同的操作。 這樣做會花費您O(N)的時間。 因此,在實際應用中在數組上使用鍊錶是有利的。 鍊錶實現了所有這些目的,因為它不將數據存儲為連續的塊。 它將每個元素存儲在某個隨機位置。 但是,它如何維持秩序? 這個問題的答案是,鍊錶使用了指針。 每個節點都指向鏈接列表中的另一個節點,因此,我們不必分配單個塊更改,而這又需要進行大量計算。

如果給出了頭指針

現在問題要求我們 刪除節點。 通常,給我們一個節點的地址,並要求我們刪除鍊錶中的下一個節點。 但是在這裡,我們需要刪除一個地址已提供給我們的節點。 解決此問題的一種方法是先遍歷整個鍊錶。 然後,存儲每個節點的父節點,並在作為輸入提供的節點處中斷循環。 這樣一來,最終我們有了要刪除的節點的父節點。 因此,現在的問題變成了簡單刪除鍊錶中一個給出了父級地址的節點。 但這將使我們付出O(N)的代價。 但是,只有當您具有頭指針時,才可以使用這種方式。

解決方案

解決“沒有頭指針的情況下從鏈接列表中刪除節點”問題的方法是交換要刪除的節點和鏈接列表中的下一個節點的數據。 鍊錶中的每個節點都存儲下一個節點。 因此,此操作僅具有O(1)時間複雜度。 現在,當數據已交換時。 再一次,我們已將問題更改為刪除給出了父級地址的節點。 因此,現在我們可以更輕鬆地解決問題。 但是在某些情況下,我們必須刪除端節點,但無法刪除端節點。 因為沒有下一個節點。

推薦碼

C ++代碼刪除沒有頭指針的節點

#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;
}

void deletedNode(node* &head, node* toBeDeleted){
  if(toBeDeleted == NULL)
    return;
  else{
    if(toBeDeleted->next == NULL){
      cout<<"Last node can't be freed";
    }
    // store or swap but ( the data of current node will be deleted)
    toBeDeleted->data = toBeDeleted->next->data;
    toBeDeleted->next = toBeDeleted->next->next;
  }
}

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;
  }
  deletedNode(head, toBeDeleted);

  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 5 6 7

刪除沒有頭指針的節點的Java代碼

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 deletedNode(node head, node toBeDeleted){
    if(toBeDeleted == null)
      return null;
    else{
      if(toBeDeleted.next == null){
        System.out.print("Last node can't be freed");
        return null;
      }
      // store or swap but ( the data of current node will be deleted)
      toBeDeleted.data = toBeDeleted.next.data;
      toBeDeleted.next = toBeDeleted.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);
    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);
 
    System.out.print("Old Linked List: ");
    node tmp = head;
    while(tmp != null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
    head = deletedNode(head, toBeDeleted);
 
    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 5 6 7

複雜度分析

時間複雜度

O(1), 因為交換可能會在固定時間內中斷。 然後我們只是更改一些指針,這又是一個恆定時間的操作。

空間複雜度

O(1), 因為我們使用的變量不取決於鍊錶中節點的數量。 因此,空間複雜度也是恆定的。