資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究從給定的連結串列中生成一個新的連結串列，新連結串列的每個節點的值為原連結串列中節點對的平方差的最大值。
連結串列是一種線性資料結構，由節點組成，每個節點在主記憶體中並不連續存在，而是每個節點包含下一個節點的地址。給定一個長度為偶數的連結串列，我們需要建立一個新的連結串列，該連結串列的節點數為給定連結串列的一半，每個節點的值為給定連結串列中節點值的平方差，按降序排列。
示例
讓我們透過輸入輸出示例來理解這個問題：
輸入
Given linked list: 1 -> 4 -> 6 -> 9 -> 2 -> 5 -> null
輸出
80 -> 32 -> 9 -> null
解釋
如果我們對所有元素進行排序，我們將得到1, 2, 4, 5, 6, 9，然後我們將從第一個元素到最後一個元素配對，第二個元素到倒數第二個元素配對，依此類推。
方法
在這個問題中，我們需要找到平方差的降序最大值，因此，為了獲得最大差值，我們需要對連結串列的元素進行排序，第一個和最後一個元素的平方差將最大。
首先，我們將建立一個類，該類將包含一個整數變數和一個指標，用於儲存節點的值和指向下一個節點的指標。
我們將定義一些基本函式，例如列印函式，用於列印連結串列的所有元素，以及建立連結串列的函式。
在主函式中，我們將建立連結串列，然後呼叫輔助函式，該函式將返回新連結串列的頭節點。
在輔助函式中，首先我們將定義一個雙端佇列(deque)，它將包含連結串列的所有元素，然後我們將對雙端佇列進行排序。
因為我們需要第一個和最後一個元素來計算差值，所以雙端佇列是最佳選擇，因為我們可以從兩端彈出元素，我們也可以在這裡使用向量，並使用兩個指標來處理。
排序後，我們將迭代所需次數以建立新的連結串列，並返回其頭節點。
示例
#include <bits/stdc++.h>
using namespace std;
// Linked list node
class Node{
public:
int data; // variable to store data
Node* next; // pointer to store the address of next element
// constuctor to create a new object or node
Node(int val){
data = val;
next = nullptr;
}
};
// function to add elements in the linked list
Node* push(Node* head, int val){
// create a new node
Node* new_node = new Node(val);
// add the data of the next node
new_node->next = head;
// move the head to next position
head = new_node;
return head;
}
// function to print all the elements of the linked list
void print(Node* head){
Node* temp = head; // assign head to temporary variable
// iterating over the linked list using temp variable
while(temp){
// print current data
cout << temp->data << " -> ";
// iterate to next pointer
temp = temp->next;
}
cout<<"NULL"<<endl;
}
// function to get new linked list
Node* getLL(Node* head){
// Stores the node of linekd list in deque to iterate later
deque<int> dq;
Node* temp = head;
// store the data in head
while(temp != nullptr){
dq.push_back(temp->data);
temp = temp->next;
}
// sort the current dq
sort(dq.begin(), dq.end());
// new_head is the head of the new linked list
Node* new_head = nullptr;
Node* prev_node = nullptr;
// getting size of new linked list
int sz = dq.size() / 2;
// traversing over the size
while (sz--) {
int front = dq.front();
int back = dq.back();
// getting the differnce of squares
int cur = back*back - front*front;
// adding new value to new linked list
Node* temp = new Node(cur);
if(new_head == nullptr){
new_head = temp;
prev_node = temp;
} else {
prev_node->next = temp;
prev_node = temp;
}
// remove the first and last elements of the deque
dq.pop_back();
dq.pop_front();
}
// return the new linked list head
return new_head;
}
int main(){
struct Node* head = NULL;
// Given Linked list
head = push(head, 9);
head = push(head, 5);
head = push(head, 6);
head = push(head, 2);
head = push(head, 4);
head = push(head, 1);
cout<<"The given linked list is: "<<endl;
print(head);
// calling to function to get the new linked list
Node* newLL = getLL(head);
// print the new Linked list
cout<<"The new linked list is: "<<endl;
print(newLL);
return 0;
}
輸出
The given linked list is: 1 -> 4 -> 2 -> 6 -> 5 -> 9 -> NULL The new linked list is: 80 -> 32 -> 9 -> NULL
時間和空間複雜度
上述程式碼的時間複雜度為O(N*log(N))，其中N為給定連結串列的大小，由於對雙端佇列進行排序，我們得到了對數因子。
上述程式碼的空間複雜度為O(N)，因為我們使用了額外的雙端佇列空間來儲存值。
結論
在本教程中，我們實現了一個程式，用於從給定的偶數大小的連結串列建立一個新連結串列，其大小為原連結串列的一半。在新連結串列中，每個節點都包含節點值平方差的降序排列。我們使用了雙端佇列來儲存所有元素，然後對其進行排序以獲取雙端佇列的第一個和最後一個元素。程式碼的時間複雜度為O(N*log(N))，空間複雜度為線性。
52 次瀏覽
