2

我有一个链表，现在我想遍历它，每次前进时，我都会将当前节点移动到链表的开头，如下所示：

4 5 3 2 7
5 4 3 2 7
3 5 4 2 7
2 3 5 4 7
7 2 3 5 4

编码：

#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 *nod2 = NULL;
    node *nod_tmp = NULL;

    node *nod_next = NULL;
    node *nod_before = 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_before = nod_tmp; // save current node
        nod_next = nod_tmp->next->next; // save next node
        nod_before->next = nod_next; // link the previous with the next one
        nod_tmp->next = nod; // point the current node to the beginning of list
    }

    while(nod != NULL)
    {   
        printf("%d\n", nod->p);
        nod = nod->next;
    }
    return 0;
}
4

4 回答 4

2

认真考虑一下反转列表的 while 循环实际上在做什么。例如，假设我们有这个列表：

1 --> 2 --> 3 -->null

让我们看看你的while循环代码：

nod_tmp = nod; // nod and nod_tmp now point to 1
while (nod_tmp->next != NULL)
{
    nod_before = nod_tmp; // nod_before, nod_tmp, and nod all point to 1
    nod_next = nod_tmp->next->next; // nod_next points to 3
    nod_before->next = nod_next; // 1-->3 
    nod_tmp->next = nod; // 1-->1
}

第一个节点（仍然由 nod_tmp 引用）现在指向它自己。这不仅会导致您的 while 条件无限旋转，还会泄漏列表中的其余内存。

于 2013-01-08T14:12:48.467 回答
2 
nod_tmp = nod->next;
nod_before= nod;
while (nod_tmp != NULL)
{
     nod_before->next = nod_tmp->next;
     nod_tmp->next = nod;
     nod = nod_tmp;
     nod_tmp = nod_before->next;
}

将您的第二个循环更改为上面的这个循环。注意node_tmp指向头部之后的第二个节点并nod_before指向第一个节点。这样可以避免无限循环。

于 2013-01-08T14:30:12.060 回答
0

无限循环就在这里：

while (nod_tmp->next != NULL)
    {
        nod_before = nod_tmp; // save current node
        nod_next = nod_tmp->next->next; // save next node
        nod_before->next = nod_next; // link the previous with the next one
        nod_tmp->next = nod; // point the current node to the beginning of list
    }
于 2013-01-08T14:06:15.073 回答
0 
#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 *nod2 = NULL; //header of the linked list
    node *nod_tmp = 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 = nod2;
        nod2 = nod_tmp;
    }

    nod = nod2;

    printf("Linked list order before reversing:  ");
    while(nod != NULL)
    {   
        printf("%d  ", nod->p);
        nod = nod->next;
    }
    printf("\n");

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

    nod = nod2;

    printf("Linked list order after reversing:  ");
    while(nod != NULL)
    {   
        printf("%d ", nod->p);
        nod = nod->next;
    }
    printf("\n");
    return 0;
}
于 2013-01-08T14:49:55.170 回答