C语言 交换链表中的节点

Question

我有一个链表，例如以下值：4 5 3 2 7，现在我想将每个节点与前一个节点交换，如下所示：

4 5 3 2 7 // this beginning of list
5 4 3 2 7
5 3 4 2 7
5 3 2 4 7
5 3 2 7 4 // the list should now become like this

但不幸的是，当我解析输出时，我陷入了无限循环：

#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
    int p;
    struct _node *next;
} node;
main(int argc, char **argv)
{
    int i, n;
    node *nod = NULL;
    node *nod_tmp = NULL;
    node *nod2 = NULL;
    printf("Enter n: ");
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        nod_tmp = (node *)malloc(sizeof(node));
        scanf("%d", &nod_tmp->p);
        nod_tmp->next = nod;
        nod = nod_tmp;
    }
    i = 0;
    while(i < n)
    {   
        nod_tmp = nod;
        nod = nod->next;
        nod->next = nod_tmp;
        ++i;
    }
    while(nod != NULL)
    {   
        printf("%dn", nod->p);
        nod = nod->next;
    }
    return 0;
}  

Answer 1

这看起来很奇怪：

while(i < n)
{   
    nod_tmp = nod;
    nod = nod->next;
    nod->next = nod_tmp;
    ++i;
}

基本上，您正在循环 2 个项目将它们相互分配。您需要查看此内容。

编辑

好的为你写的，似乎正在工作。(我通过实际按对交换列表元素来做到这一点(。

/// reading and stuff...
node *prev = NULL, *start = nod->next;
for(int i = 0; i < n - 1; ++i)
{
    // look at this part, it makes everything obvious
    node *a = nod, *b = nod->next, *c = nod->next->next;
    b->next = a;
    a->next = c;
    nod = a; // changing the current node to next
    if(i == 0)
            {
        start = prev = b; // saving an actual start
            }
    else
    {
        prev->next = b;
        prev = prev->next;
    }
    // printing state to be sure
    for(node *tmp_start = start; tmp_start != NULL; tmp_start = tmp_start->next)
        printf("%d ", tmp_start->p);
    printf("n");
}
printf("Final answer:n");
while(start != NULL)
{   
    printf("%d ", start->p);
    start = start->next;
}

您需要以相反的顺序输入数据(或稍微更改读取功能(

使用示例：

Enter n: 5 7 2 3 5 4
5 4 3 2 7
5 3 4 2 7
5 3 2 4 7
5 3 2 7 4
Final answer:
5 3 2 7 4 

Answer 2

您的交换代码是错误的。 应该是这样的：

i = 1;
nod2 = nod;
while(i < n)
{   
    nod_tmp = nod2->next;
    nod2->next = nod_tmp->next;
    nod_tmp->next = nod2;
    ++i;
}

或者，由于交换每个对基本上会将第一个元素推到最后，因此您可以这样做：

nod_tmp = nod;
while (nod_tmp->next != NULL)
{
    nod_tmp = nod_tmp->next;
}
// nod_tmp now points to the last element
nod_tmp->next = nod;          // loop from the last element back to the first
nod = nod->next;              // move the list pointer to the second element
nod_tmp->next->next = NULL;   // break the loop at the new last element

此外，您可能希望查看输入代码。 如前所述，它将以与输入的相反顺序使用值构建列表，因为它总是将下一个值添加到列表的头部。

更新

为了避免潜在的seg_faults可以在没有计数器的情况下重写上面的第一个循环，如下所示：

nod2 = nod;
nod_tmp = nod2->next;
while(nod_tmp != NULL)
{   
    nod2->next = nod_tmp->next;
    nod_tmp->next = nod2;
    nod_tmp = nod2->next;
}

更新 2

下面是执行所需操作的完整代码。 它不是交换每对节点，而是将第一个节点推送到列表的末尾。 我还修复了输入循环，以便列表以正确的顺序构建。

#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
    int p;
    struct _node *next;
} node;
main(int argc, char **argv)
{
    int i, n;
    node *nod = NULL;
    node *nod_tmp = NULL;
    node *nod2 = NULL;
    printf("Enter n: ");
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        nod_tmp = (node *)malloc(sizeof(node));
        scanf("%d", &nod_tmp->p);
        if (i == 0)
        {
            nod = nod2 = nod_tmp;
        }
        nod2->next = nod_tmp;
        nod2 = nod_tmp;
    }
    nod_tmp = nod;
    while (nod_tmp->next != NULL)
    {
        nod_tmp = nod_tmp->next;
    }
    // nod_tmp now points to the last element
    nod_tmp->next = nod;          // loop from the last element back to the first
    nod = nod->next;              // move the list pointer to the second element
    nod_tmp->next->next = NULL;   // break the loop at the new last element
    while(nod != NULL)
    {   
        printf("%dn", nod->p);
        nod = nod->next;
    }
    return 0;
}   

Answer 3

让我们按照这个循环：

while(i < n)
{   
    nod_tmp = nod;         // 1
    nod = nod->next;       // 2
    nod->next = nod_tmp;   // 3
    ++i;
}

1. nod_tmp和nod现在指向同一节点。
2. nod现在指向nod->next(所以nod == nod_temp->next(
3. nod->next现在指向not_temp这是nod的旧地址。

现在nod->next指向nod的旧地址(nod_temp也指向该地址(，您有一个链表，其尾部指向其头部。

这个 while 循环可能更适合您：

nod2 = nod;
nod_tmp = nod->next;
while(nod_tmp != NULL)
{   
    nod2->next = nod_tmp->next;
    nod_tmp->next = nod2;
    nod_tmp = nod2->next;
}

Answer 4

您需要在完成交换后和打印结果之前清除列表中最后一个条目的点头>下一个。

Answer 5

c++11 way ..

编译方式： g++ --std=c++11 -Wall -Wextra mylist.cpp

#include <iostream>
#include <list>
template <class List>
void print(const List& list) {
    for (auto i : list)
        std::cout << i << ' ';
    std::cout << std::endl;
}
template <class List>
void swap(List& list) {
    auto i(list.begin());
    auto next(i);
    auto end(list.end());
    while (++next != end) {
        auto tmp = *i;
        *i++ = *next;
        *i = tmp;
        print(list);
    }
}
int main(int, char**) {
    std::list<int> list {4, 5, 3, 2, 7};
    print(list);
    swap(list);
}

Answer 6

    i = 0;
    while(i < n)
    {
        printf("%dn", nod->p);
        nod = nod->next;
        i++;
    }