如何交换单链表中两个节点的位置，只修改指针？

Question

我正在尝试将给定基于 0 的索引的单向链表的两个节点交换到其中。在我的代码中，我处理了很多情况，但这种方法仅在j-i<=2. 如果i和之间有 3 或更多的差异j，我将无法处理。
请帮助我纠正我的方法。

node* swap_nodes(node *head,int i,int j)
{
    if(j<i)
    {
        int temp;
        temp=i;
        i=j;
        j=temp;
    }
    node *prev1,*prev2,*temp1,*temp2;

    if(i==j)
    {
        return head;
    }

    if(i==0  && abs(i-j)!=1)
    {
        int n=0;
        node *temp=head;
        prev1=head;
        temp1=prev1->next;

        while(n<j-1)
        {
            temp=temp->next;
            n++;
        }

        prev2=temp;
        temp2=prev2->next;
        prev2->next=temp1;
        temp1->next=prev1;
        prev1->next=temp2->next;
        temp2->next=prev2;

        return temp2;
    }
    else if(abs(i-j)==1 && i!=0 )
    {
        int n=0;
        node *temp=head;
        while(n<i-1)
        {
            temp=temp->next;
            n++;
        }

        prev1=temp;
        temp1=prev1->next;
        n=0;

        while(n<j-i+1)
        {
            temp=temp->next;
            n++;
        }

        temp2=temp;
        prev1->next=temp2;
        temp1->next=temp2->next;
        temp2->next=temp1;

        return head;
    }
    else if(i==0 && j==1)
    {
        temp1=head;
        temp2=head->next;
        node *temp3=temp2->next;
        temp2->next=temp1;
        temp1->next=temp3;

        return temp2;
    }
    else
    {
        int n=0;
        node *temp=head;

        while(n<i-1)
        {
            temp=temp->next;
            n++;
        }

        prev1=temp;
        temp1=prev1->next;
        n=0;

        while(n<j-i)
        {
            temp=temp->next;
            n++;
        }

        prev2=temp;
        temp2=prev2->next;
        prev1->next=temp2;
        temp1->next=temp2->next;
        temp2->next=prev2;
        prev2->next=temp1;

        return head;
    }
}

Answer 1

用于交换链表中节点的指针控制的基础很简单：

• 在列表中找到指向要交换的节点的指针。这些指针之一可以是head指针，但至少有一个是next列表中的某个指针。请记住，这些是指向您要交换的节点的指针。
• 交换那些指针
• 交换next这些节点的指针以恢复列表的剩余顺序。
• 就是这样。

为此，最简单的方法是使用指向指针的指针。这避免了必须prev完全围绕指针，这使得算法比它需要的复杂得多。

你的方法很勇敢，但非常复杂。坚持上面的算法，它会变得更清楚需要什么。找到一些指向你想要交换的东西的指针，交换它们，然后交换回它们内部的下一个指针。

鉴于所有这些，算法实现如下（保留您只扫描列表一次以找到要交换的两个节点的愿望）。关于算法如何与代码匹配的注释是内联的：

node *swap_nodes(node *head, int i, int j)
{
    if (i < 0 || j < 0 || i == j)
        return head;

    // order i and j
    if (j < i)
        std::swap(i,j);

    // find the pointer pointing to i'th node.
    node **pp1 = &head;
    while (*pp1 && i-- > 0)
    {
        pp1 = &(*pp1)->next;
        --j;
    }

    // finish finding the pointer pointing to the j'th node
    node **pp2 = pp1;
    while (*pp2 && j-- > 0)
        pp2 = &(*pp2)->next;

    // if either index was out of range, at least one of these will
    //  be null, and if that's the case, no swap will happen
    if (*pp1 && *pp2)
    {
        // swap the pointers
        std::swap(*pp1, *pp2);

        // and swap *back* their next members
        std::swap((*pp1)->next, (*pp2)->next);
    }

    return head;
}

例子

如果没有一个实际的例子，这将是不公平的。下面将构建一个由十个元素组成的有序列表，编号为 1..10。然后它使用上面基于零索引的交换例程来交换各种元素，特别是交换头节点、尾节点和一些内部节点的东西，然后通过反转交换来撤消所有这些以到达我们开始的列表和。

#include <iostream>

struct node
{
    int data;
    struct node *next;

    node(int x)
        : data(x)
        , next(nullptr)
    {
    }
};

void ll_print(node const *p)
{
    while (p)
    {
        std::cout << p->data << ' ';
        p = p->next;
    }
    std::cout << '\n';
}

void ll_free(node **head)
{
    while (*head)
    {
        node *tmp = *head;
        *head = tmp->next;
        delete tmp;
    }
}

node *swap_nodes(node *head, int i, int j)
{
    if (i < 0 || j < 0 || i == j)
        return head;

    // order i and j
    if (std::min(i,j) == j)
        std::swap(i,j);

    // find the pointer pointing to i'th node.
    node **pp1 = &head;
    while (*pp1 && i-- > 0)
    {
        pp1 = &(*pp1)->next;
        --j;
    }

    // finish finding the pointer pointing to the j'th node
    node **pp2 = pp1;
    while (*pp2 && j-- > 0)
        pp2 = &(*pp2)->next;

    // if either index was out of range, at least one of these will
    //  be null, and if that's the case, no swap will happen
    if (*pp1 && *pp2)
    {
        // swap the pointers
        std::swap(*pp1, *pp2);

        // and swap *back* their next members
        std::swap((*pp1)->next, (*pp2)->next);
    }

    return head;
}

int main ()
{
    // build a forward-chained linked list of ten items

    node *head = NULL, **pp = &head;
    for (int i=1; i<=10; ++i)
    {
        *pp = new node(i);
        pp = &(*pp)->next;
    }

    // print the list
    ll_print(head);

    // swap the first and second nodes
    printf("Swapping 0,1\n");
    head = swap_nodes(head, 0, 1);
    ll_print(head);

    // swap the first and last nodes
    printf("Swapping 0,9\n");
    head = swap_nodes(head, 0, 9);
    ll_print(head);

    // swap two internal nodes
    printf("Swapping 3,6\n");
    head = swap_nodes(head, 3, 6);
    ll_print(head);
    ////////////////////////////////////////

    // this shoudl swap everything back, so it should give us
    //  what we originally had.

    // swap two internal nodes
    printf("Swapping 3,6\n");
    head = swap_nodes(head, 3, 6);
    ll_print(head);

    // swap the first and last nodes
    printf("Swapping 0,9\n");
    head = swap_nodes(head, 0, 9);
    ll_print(head);

    // swap the first and second nodes
    printf("Swapping 0,1\n");
    head = swap_nodes(head, 0, 1);
    ll_print(head);

    // release the list
    ll_free(&head);
}

输出

1 2 3 4 5 6 7 8 9 10 
Swapping 0,1
2 1 3 4 5 6 7 8 9 10 
Swapping 0,9
10 1 3 4 5 6 7 8 9 2 
Swapping 3,6
10 1 3 7 5 6 4 8 9 2 
Swapping 3,6
10 1 3 4 5 6 7 8 9 2 
Swapping 0,9
2 1 3 4 5 6 7 8 9 10 
Swapping 0,1
1 2 3 4 5 6 7 8 9 10 

概括

如果您还记得自己要做什么：交换指针，而不是节点，那么您试图避免的大多数边缘情况都会消失。诀窍是找到指向要交换的节点的指针（不是它们的值；实际的指针），并交换这些指针的值