[已解决]这个好难求指导！

a905448839

以下代码中的struct Node *reversed(struct Node *head)函数始终无法理解如何实现。。
不知道如何去生动形象理解，或者有大佬以图片或者动图或视频告知以下吗？

1. struct Node *reversed(struct Node *head)
   
2. {
   
3.     struct Node *pre;         //pre指针表示当前节点的前一个节点
   
4.     struct Node *cur;         //cur指针表示当前节点
   
5.     pre = NULL;               //初始的前一个节点为NULL，因为反转后最后一个节点为NULL
   
6.     cur = head;               //初始的当前节点为头结点
   
7.    
   
8.     while(cur)                //从头结点遍历全部节点
   
9.     {
   
10.         struct Node* next = cur->next;  //定义了一个Node结构体的指针next变量 用来保存下一个节点的指针
    
11.             //在while循环体内 next是个局部变量 每次循环结束他都会被摧毁 不会影响链表其他部位
    
12.         cur->next = pre;                //将当前节点的指针指向前一个节点
    
13.         pre = cur;                      //更新前一个节点为当前节点
    
14.         cur = next;                     //当前节点指向下一个节点
    
15.     }
    
16.     return pre;   //返回反转后的头结点指针
    
17. }

复制代码

完整代码：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. struct Node
   
5. {
   
6.         int value;
   
7.         struct Node *next;
   
8. };
   
9. 
   
10. void printNode(struct Node *head);
    
11. void insertNode(struct Node **head, int value);
    
12. struct Node *reversed(struct Node *head);
    
13. 
    
14. void insertNode(struct Node **head, int value)
    
15. {
    
16.         struct Node *previous;//current上一个节点的指针
    
17.         struct Node *current;//当前位置   指向比value大的节点指针
    
18.         struct Node *new;
    
19.        
    
20.         current = *head;
    
21.         previous = NULL;
    
22.        
    
23.         while(current != NULL && current->value < value)
    
24.         {
    
25.                 previous = current;
    
26.                 current = current->next;
    
27.         }
    
28.         new = (struct Node *)malloc(sizeof(struct Node));
    
29.         if(new == NULL)
    
30.         {
    
31.                 printf("内存分配失败！\n");
    
32.                 exit(1);
    
33.         }
    
34.        
    
35.         new->value = value;
    
36.         //previous->next = new;  这个先不用写 后面要判断他是不是为NULL
    
37.         new->next = current;
    
38.        
    
39.         if(previous == NULL)//previous为NULL只有一种情况（因为把current赋值给previous 且current不为NULL才能赋值）
    
40.                             //所以current本身一进来就为NULL 空的单链表
    
41.         {
    
42.                 *head = new;//所以将*head指针修改为new    这个new是唯一一个节点
    
43. 
    
44.         }
    
45.         else
    
46.         previous->next = new;
    
47. 
    
48. 
    
49. }
    
50. 
    
51. void printNode(struct Node *head)
    
52. {
    
53.         struct Node *current;
    
54.        
    
55.         current = head;
    
56.         while(current != NULL)
    
57.         {
    
58.                 printf("%d ",current->value);
    
59.                 current = current->next;
    
60. 
    
61.         }
    
62.         putchar('\n');
    
63. 
    
64. }
    
65. 
    
66. 
    
67. struct Node *reversed(struct Node *head)
    
68. {
    
69.     struct Node *pre;         //pre指针表示当前节点的前一个节点
    
70.     struct Node *cur;         //cur指针表示当前节点
    
71.     pre = NULL;               //初始的前一个节点为NULL，因为反转后最后一个节点为NULL
    
72.     cur = head;               //初始的当前节点为头结点
    
73.    
    
74.     while(cur)                //从头结点遍历全部节点
    
75.     {
    
76.         struct Node* next = cur->next;  //定义了一个Node结构体的指针next变量 用来保存下一个节点的指针
    
77.             //在while循环体内 next是个局部变量 每次循环结束他都会被摧毁 不会影响链表其他部位
    
78.         cur->next = pre;                //将当前节点的指针指向前一个节点
    
79.         pre = cur;                      //更新前一个节点为当前节点
    
80.         cur = next;                     //当前节点指向下一个节点
    
81.     }
    
82.     return pre;   //返回反转后的头结点指针
    
83. }
    
84. 
    
85. 
    
86. int main(void)
    
87. {
    
88.         struct Node *head = NULL;
    
89.         int input;
    
90.        
    
91.         while(1)
    
92.         {
    
93.                 printf("请输入一个整数（输入-1表示结束）：");
    
94.                 scanf("%d",&input);
    
95.                 if(input == -1)
    
96.                 {
    
97.                         break;       
    
98.                 }
    
99.                 insertNode(&head, input);
    
100.                 printNode(head);       
     
101.         }  
     
102. 
     
103.         printf("\n下面将单链表a原地反转...\n");
     
104.     head = reversed(head);
     
105.     printNode(head);
     
106. 
     
107. 
     
108.         return 0;
     
109. }
     

复制代码

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-9 21:59:31

a905448839 发表于 2023-4-9 21:54
我在草稿纸上演算
第一轮：
next = 2

对的

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> NULL

首先，我们定义两个指针，pre 和 cur。pre 表示当前节点的前一个节点，而 cur 表示当前节点。

1、初始化 pre 和 cur：
pre = NULL
cur = head（也就是 1）

2、进入 while 循环，开始遍历链表的每个节点。在每次循环中，我们将执行以下操作：

a) 用 next 临时存储 cur 的下一个节点，以便在后续操作中使用。在这个例子中，第一次循环时，next 将指向 2。

b) 将 cur（当前节点）的 next 指针指向 pre（前一个节点）。第一次循环时，将 1 的 next 指针指向 NULL。

c) 更新 pre 和 cur。将 pre 设置为 cur，将 cur 设置为 next。在这个例子中，第一次循环后，pre 变为 1，cur 变为 2。

3、第二轮循环：
a) next = 3
b) 将 cur（当前节点，即 2）的 next 指针指向 pre（前一个节点，即 1）。现在链表看起来像这样：NULL <- 1 <- 2 3 -> 4 -> NULL
c) 更新 pre 和 cur。pre 变为 2，cur 变为 3。

4、第三轮循环：
a) next = 4
b) 将 cur（当前节点，即 3）的 next 指针指向 pre（前一个节点，即 2）。现在链表看起来像这样：NULL <- 1 <- 2 <- 3 4 -> NULL
c) 更新 pre 和 cur。pre 变为 3，cur 变为 4。

5、第四轮循环：
a) next = NULL
b) 将 cur（当前节点，即 4）的 next 指针指向 pre（前一个节点，即 3）。现在链表看起来像这样：NULL <- 1 <- 2 <- 3 <- 4
c) 更新 pre 和 cur。pre 变为 4，cur 变为 NULL。

6、cur 变为 NULL，循环结束。此时，链表已反转：NULL <- 1 <- 2 <- 3 <- 4

最后，返回 pre（也就是新链表的头结点，也就是 4）。

跳转到最佳答案楼层

isdkz

这个代码的主要目的是实现链表的反转。为了帮助您更好地理解这个过程，我将逐步向您解释代码以及代码的逻辑。为了进一步说明这个过程，我还将使用一些简单的示例进行说明。

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> NULL

首先，我们定义两个指针，pre 和 cur。pre 表示当前节点的前一个节点，而 cur 表示当前节点。

1、初始化 pre 和 cur：
pre = NULL
cur = head（也就是 1）

2、进入 while 循环，开始遍历链表的每个节点。在每次循环中，我们将执行以下操作：

a) 用 next 临时存储 cur 的下一个节点，以便在后续操作中使用。在这个例子中，第一次循环时，next 将指向 2。

b) 将 cur（当前节点）的 next 指针指向 pre（前一个节点）。第一次循环时，将 1 的 next 指针指向 NULL。

c) 更新 pre 和 cur。将 pre 设置为 cur，将 cur 设置为 next。在这个例子中，第一次循环后，pre 变为 1，cur 变为 2。

3、继续循环，直到 cur 变为 NULL，即遍历完整个链表。

在完成循环后，链表将被反转，如下所示：NULL <- 1 <- 2 <- 3 <- 4

最后，返回 pre（也就是新链表的头结点，也就是 4）。

在这个过程中，我们通过更新每个节点的 next 指针，使其指向前一个节点，从而实现链表的反转。希望这种解释方式能帮助您更好地理解这段代码的逻辑。

为了更好地理解这个过程，您可以在纸上画出链表的每一步操作，观察指针如何在每次迭代中更新。这将有助于您更直观地了解链表反转的过程。

a905448839

isdkz 发表于 2023-4-9 21:41
这个代码的主要目的是实现链表的反转。为了帮助您更好地理解这个过程，我将逐步向您解释代码以及代码的逻辑 ...

我在草稿纸上演算
第一轮：
next = 2
cur->next =  NULL
pre = 1
cur = 2

第二轮：
next = NULL
cur->next = 1
pre = 2
cur = NULL

cur = NULL是不是循环结束了呢?

isdkz

a905448839 发表于 2023-4-9 21:54
我在草稿纸上演算
第一轮：
next = 2

对的

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> NULL

首先，我们定义两个指针，pre 和 cur。pre 表示当前节点的前一个节点，而 cur 表示当前节点。

1、初始化 pre 和 cur：
pre = NULL
cur = head（也就是 1）

2、进入 while 循环，开始遍历链表的每个节点。在每次循环中，我们将执行以下操作：

a) 用 next 临时存储 cur 的下一个节点，以便在后续操作中使用。在这个例子中，第一次循环时，next 将指向 2。

b) 将 cur（当前节点）的 next 指针指向 pre（前一个节点）。第一次循环时，将 1 的 next 指针指向 NULL。

c) 更新 pre 和 cur。将 pre 设置为 cur，将 cur 设置为 next。在这个例子中，第一次循环后，pre 变为 1，cur 变为 2。

3、第二轮循环：
a) next = 3
b) 将 cur（当前节点，即 2）的 next 指针指向 pre（前一个节点，即 1）。现在链表看起来像这样：NULL <- 1 <- 2 3 -> 4 -> NULL
c) 更新 pre 和 cur。pre 变为 2，cur 变为 3。

4、第三轮循环：
a) next = 4
b) 将 cur（当前节点，即 3）的 next 指针指向 pre（前一个节点，即 2）。现在链表看起来像这样：NULL <- 1 <- 2 <- 3 4 -> NULL
c) 更新 pre 和 cur。pre 变为 3，cur 变为 4。

5、第四轮循环：
a) next = NULL
b) 将 cur（当前节点，即 4）的 next 指针指向 pre（前一个节点，即 3）。现在链表看起来像这样：NULL <- 1 <- 2 <- 3 <- 4
c) 更新 pre 和 cur。pre 变为 4，cur 变为 NULL。

6、cur 变为 NULL，循环结束。此时，链表已反转：NULL <- 1 <- 2 <- 3 <- 4

最后，返回 pre（也就是新链表的头结点，也就是 4）。