資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究用於從已排序連結串列中刪除重複項的 JavaScript 程式
連結串列是一種線性資料結構，我們給定一個包含整數的已排序連結串列。可能存在一些重複的數字，我們必須將它們刪除。由於給定的連結串列已排序，我們可以簡單地迭代它，並使用 while 迴圈從中刪除重複的節點。我們將實現一個正確的程式碼來更好地理解邏輯，並討論時間和空間複雜度。
示例
Given linked list is: 1-> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 5 -> 5-> 6-> null Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
解釋 − 給定的連結串列已排序，這使得查詢重複元素變得容易，我們可以透過跳過與前一個值相等的值來刪除它們。
讓我們看看程式碼的方法
方法
我們將遵循以下步驟來解決問題：
首先，我們將建立一個類來提供連結串列節點的結構。
其次，我們將建立函式來列印連結串列並將新節點新增到現有連結串列中。
我們將建立一個函式來傳遞我們想要從中刪除重複元素的連結串列的頭，它將返回新連結串列的頭。
首先，我們將檢查連結串列是否為空或其大小是否等於 1。在這些情況下，我們將按原樣返回頭部。
我們將建立兩個變數，一個指向頭部，另一個指向頭部的下一個節點。
如果當前節點和下一個節點的值相等，那麼我們將下一個節點移動到它的下一個節點，並更新當前節點的下一個節點的地址。
否則，我們將移動到下一個節點，並將下一個節點移動到它的下一個節點。
最後，我們將返回頭部並列印其中存在的值。
示例
為了更好地理解，讓我們在程式碼中實現給定的步驟
// class to provide structure to linked list node
class Node{
constructor(val){
this.value = val
this.next = null
}
}
// function to print the linked list
function print(head){
var temp = head;
if(head == null){
console.log("The given linked list is empty");
} else {
var ans = ""
while(temp.next != null){
ans += temp.value;
ans += " -> "
temp = temp.next
}
ans += temp.value
ans += " -> null"
}
console.log(ans)
}
// function to add data in linked list
function add(data, head, tail){
var new_node = new Node(data);
if(head == null){
head = new_node
return new_node
} else {
tail.next = new_node;
return new_node
}
}
// function to remove the duplicate numbers
function removeDupli(head){
// if linked list is empty
if(head == null){
return head;
}
// if linked list is of size one
if(head.next == null){
return head;
}
var temp = head
var next = head.next
while(next != null){
if(temp.value == next.value){
next = next.next;
temp.next = next;
} else {
next = next.next;
temp = temp.next;
}
}
return head;
}
// defining linked list
var head = new Node(1)
var tail = head
tail = add(2,head, tail)
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
console.log("The given linked list is: ")
print(head)
// calling function to remove duplicate elements
head = removeDupli(head)
console.log("The Linked list after removal of duplicate integers is: ")
print(head)
時間和空間複雜度
上述程式碼的時間複雜度為 O(N)，其中 N 是給定連結串列中的節點總數。時間複雜度是線性的，因為我們只遍歷了連結串列一次。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
結論
在本教程中，我們實現了一個 JavaScript 程式，用於從給定的已排序連結串列中刪除重複元素。由於連結串列已排序，這意味著所有重複元素都彼此相鄰，可以透過遍歷它輕鬆刪除。我們實現的程式的時間複雜度為 O(N)，空間複雜度為 O(1)。
更新於：2023年4月12日
286 次瀏覽
廣告