C++程序 在不交换数据的情况下交换链表中的节点

给定一个链表和其中的两个键，交换给定键的两个节点。通过改变链接来交换节点。当数据包含许多字段时，交换节点的数据可能在许多情况下非常昂贵。

可以假设链表中所有的键都是不同的。

示例：

输入： 10->15->12->13->20->14，x=12，y=20
输出： 10->15->20->13->12->14

输入： 10->15->12->13->20->14，x=10，y=20
输出： 20->15->12->13->10->14

输入： 10->15->12->13->20->14，x=12，y=13
输出： 10->15->13->12->20->14

这看起来是一个简单的问题，但是它有以下几种情况需要处理。

1. x和y可能相邻，也可能不相邻。
2. x或y可能是头节点。
3. x或y可能是尾节点。
4. x和/或y可能不在链表中。

如何编写一个可处理上述所有情况的干净工作代码呢？

首先需要在给定的链表中搜索x和y。如果它们中的任何一个不存在，则返回。在搜索x和y时，跟踪当前和上一个指针。首先改变前一个指针的下一个指针，然后改变当前指针的下一个指针。

以下是上述方法的实现。

// C++程序，交换链表中的结点而不是交换结点的字段。
#include <bits/stdc++.h>
using namespace std;

// 链表结点
class Node{
  public:
  int data;
  Node* next;
};

// 通过改变链接来交换链表中的结点x和y
void swapNodes(Node** head_ref, int x, int y){
  // 如果x和y相同，就没什么要做的
  if (x == y) return;

  // 搜索x（跟踪prevX和CurrX）
  Node *prevX = NULL, *currX = *head_ref;
  while (currX && currX->data != x){
    prevX = currX;
    currX = currX->next;
  }

  // 搜索y（跟踪prevY和CurrY）
  Node *prevY = NULL, *currY = *head_ref;
  while (currY && currY->data != y){
    prevY = currY;
    currY = currY->next;
  }

  // 如果x或y没有找到，就没什么要做的
  if (currX == NULL || currY == NULL) return;

  // 如果x不是链表头
  if (prevX != NULL) prevX->next = currY;
  else *head_ref = currY;

  // 如果y不是链表头
  if (prevY != NULL) prevY->next = currX;
  else *head_ref = currX;

  // 交换下一个指针
  Node* temp = currY->next;
  currY->next = currX->next;
  currX->next = temp;
}

// 在链表的开头添加一个结点
void push(Node** head_ref, int new_data){
  // 分配结点
  Node* new_node = new Node();

  // 放入数据
  new_node->data = new_data;

  // 将旧链表链接到新结点上
  new_node->next = (*head_ref);

  // 将头指针移动到指向新结点
  (*head_ref) = new_node;
}

// 打印给定链表中的结点
void printList(Node* node){
  while (node != NULL){
    cout << node->data << " ";
    node = node->next;
  }
}

// 主函数
int main(){
  Node* start = NULL;

  /* 构建链表为：
   1->2->3->4->5->6->7 */
  push(&start;, 7);
  push(&start;, 6);
  push(&start;, 5);
  push(&start;, 4);
  push(&start;, 3);
  push(&start;, 2);
  push(&start;, 1);

  cout << "Linked list before calling swapNodes() ";
  printList(start);
  swapNodes(&start;, 4, 3);
  cout << "Linked list after calling swapNodes() ";
  printList(start);
  return 0;
}
// 本示例由rathbhupendra提供```  

输出：

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 1 2 4 3 5 6 7 

时间复杂度: O(n)

辅助空间: O(1)

优化: 上述代码可以优化为在单次遍历中搜索x和y。使用两个循环使程序简单。

更简单的方法：

// C++ program to swap two given nodes
// of a linked list
#include <iostream>

using namespace std;

// A linked list node class
class Node
{
    public:
    int data;
    class Node* next;

    // constructor
    Node(int val, Node* next)
        : data(val)
        , next(next)
    {
    }

    // print list from this
    // to last till null
    void printList()
    {
        Node* node = this;

        while (node != NULL)
        {
            cout << node->data << " ";
            node = node->next;
        }

        cout << endl;
    }
};

// Function to add a node
// at the beginning of List
void push(Node** head_ref,
        int new_data)
{
    // Allocate node
    (*head_ref) = new Node(new_data,
                        *head_ref);
}

void swap(Node*& a, Node*& b)
{
    Node* temp = a;
    a = b;
    b = temp;
}

void swapNodes(Node** head_ref,
            int x, int y)
{
    // Nothing to do if x and
    // y are same
    if (x == y)
        return;

    Node **a = NULL, **b = NULL;

    // Search for x and y in the linked list
    // and store their pointer in a and b
    while (*head_ref)
    {
        if ((*head_ref)->data == x)
        {
            a = head_ref;
        }

        else if ((*head_ref)->data == y)
        {
            b = head_ref;
        }

        head_ref = &((*head_ref)->next);
    }

    // If we have found both a and b
    // in the linked list swap current
    // pointer and next pointer of these
    if (a && b)
    {
        swap(*a, *b);
        swap(((*a)->next), ((*b)->next));
    }
}

// Driver code
int main()
{
    Node* start = NULL;

    // The constructed linked list is:
    // 1->2->3->4->5->6->7
    push(&start, 7);
    push(&start, 6);
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);

    cout << "Linked list before calling swapNodes() ";
    start->printList();
    swapNodes(&start, 6, 1);
    cout << "Linked list after calling swapNodes() ";
    start->printList();
}

输出:

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 6 2 3 4 5 1 7 

时间复杂度： O（n）

辅助空间： O（1）