链表 | 第6课（交换结点而不交换数据）

发表于

提供一个链表和两个key, 交换这两个key的结点。结点可以通过修改连接进行交换。而交换数据通常代价会很大, 因为数据可能含有很多内容。

假设链表里的所有key都是不同的。

例子:

Input:  10->15->12->13->20->14,  x = 12, y = 20
Output: 10->15->20->13->12->14

Input:  10->15->12->13->20->14,  x = 10, y = 20
Output: 20->15->12->13->10->14

Input:  10->15->12->13->20->14,  x = 12, y = 13
Output: 10->15->13->12->20->14

这个看起来很简单, 但是下面的场景处理起来很有趣。

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

如何写代码来处理上述所有的情况？

想法是，先在链表里搜索 x 和 y. 如果有一个没有找到, 就返回。在搜索 x 和 y 的时候, 跟踪当前和前驱指针。首先改变前驱指针的后继, 然后修改当前指针的后继。下面是 C 语言实现的方法。

#include<stdio.h>
#include<stdlib.h>

/* 链表结点 */
struct Node
{
    int data;
    struct Node *next;
};

void swapNodes(struct Node **head_ref, int x, int y)
{
   // 如果x 和 y 相等，直接返回
   if (x == y) return;

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

   // 搜索 y (跟踪 prevY 和 CurrY
   struct 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 // 否则 y 变成新的头结点
       *head_ref = currY;  

   // 如果 y 不是头结点
   if (prevY != NULL)
       prevY->next = currX;
   else  // 否则 x 变成新的头结点
       *head_ref = currX;

   // 交换后继指针
   struct Node *temp = currY->next;
   currY->next = currX->next;
   currX->next  = temp;
}

void push(struct Node** head_ref, int new_data)
{
    /* 分配结点 */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

    /* 指定数据  */
    new_node->data  = new_data;

    /* 把新结点和老的链表相连 */
    new_node->next = (*head_ref);

    /* 新结点变成头结点 */
    (*head_ref)    = new_node;
}

/* 打印链表结点 */
void printList(struct Node *node)
{
    while(node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}

/* 测试函数 */
int main()
{
    struct 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);

    printf("\n Linked list before calling swapNodes() ");
    printList(start);

    swapNodes(&start, 4, 3);

    printf("\n Linked list after calling swapNodes() ");
    printList(start);

    return 0;
}


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

优化: 上面的代码可以优化，x 和 y 单独遍历。两个循环看起来比较简单。

更简单的方法

#include <iostream>

using namespace std;

// 结点类
class Node {

public:
    int data;
    class Node* next;

    // 构造器
    Node(int val, Node* next)
        : data(val), next(next)
    {
    }

    // 打印链表
    void printList()
    {

        Node* node = this;

        while (node != NULL) {

            cout << node->data;
            node = node->next;
        }

        cout << endl;
    }
};


void push(Node** head_ref, int new_data)
{

    // 分配结点
    (*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)
{

    // 如果 x 和 y 相等，返回
    if (x == y)
        return;

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

    // 在链表里搜索x 和 y
    // 然后保存它们的指针为 a 和 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);
    }

    // 如果发现 a 和 b
    // 交换当前指针以及它们的后继指针
    if (a && b) {

        swap(*a, *b);
        swap(((*a)->next), ((*b)->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() ";
    start->printList();

    swapNodes(&start, 6, 3);

    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() 1 2 6 4 5 3 7