数据结构
网络
关系数据库管理系统 (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 次浏览
