C++ 从给定的链表生成由节点对的差平方组成的链表

链表是一种线性数据结构，由节点组成，每个节点都不以连续形式存在于主内存中，而是每个节点包含下一个节点的地址。给定一个长度为偶数的链表，我们需要创建一个新的链表，其中包含给定链表节点数量的一半，并且每个节点的值包含给定链表节点的平方差，按降序排列。

示例

让我们通过一个输入输出示例来理解问题 –

输入

Given linked list: 1 -> 4 -> 6 -> 9 -> 2 -> 5 -> null

输出

80 -> 32 -> 9 -> null

解释

如果我们将所有元素排序，我们会得到1、2、4、5、6、9，然后我们将从第一个元素到最后一个元素，第二个元素到倒数第二个元素，依此类推，制作成对。

方法

在这个问题中，我们需要找到按照降序排列的平方之间的最大差值，所以为了得到最大差值，我们需要对链表的元素进行排序，第一个和最后一个元素的平方值之间的差值最大。

• 首先，我们将创建一个类，它将包括整数变量和一个指针，用于保存节点的值和指向下一个节点的指针。

• 我们将定义一些基本的函数，如打印函数来打印链表的所有元素和创建链表的函数。

• 在主函数中，我们将创建链表，然后调用辅助函数，该函数将返回新链表的头部。

• 在辅助函数中，首先我们将定义一个deque，其中包含链表的所有元素，然后我们将对deque进行排序。

• 由于我们需要计算差值的第一个和最后一个元素，所以deque是最好的选择，因为我们可以从两端弹出元素，我们也可以在这里使用vector，并且通过使用两个指针来处理它。

• 排序后，我们将根据所需的移动次数迭代创建新链表，并返回其头部。

示例

#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是给定链表的大小，因为需要对deque进行排序，所以存在对数因子。

上述代码的空间复杂度为O(N)，因为我们使用额外的deque空间来存储值。

结论

在本教程中，我们实现了一个程序，将给定链表的偶数大小创建为其一半大小的链表。在新的链表中，每个节点由节点值的平方差按降序组成。我们使用deque来存储所有元素，然后对其进行排序以获取deque的第一个和最后一个元素。代码的时间复杂度为O(N*log(N))，空间复杂度为线性。