用c++写一个链表逆置
时间: 2023-05-24 17:00:57 浏览: 59
以下是用 C 语言编写的链表逆置的代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node* reverseList(Node* head) {
Node *prev = NULL;
Node *curr = head;
Node *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
}
int main() {
Node *head = NULL;
Node *second = NULL;
Node *third = NULL;
// Allocate 3 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
/* Three blocks have been allocated dynamically.
We have pointers to these three blocks as head,
second and third
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+
# represents any random value.
Data is random because we haven’t assigned anything yet
*/
head->data = 1; // Assign data in first node
head->next = second; // Link first node with the second node
/* data has been assigned to the data part of the first block (block pointed by the head).
And next pointer of first block points to second.
So they both are linked.
head second third
| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/
second->data = 2; // Assign data to the second block
second->next = third; // Link second node with the third node
/* data has been assigned to the data part of the second block (block pointed by second).
And next pointer of the second block points to the third block.
So all three blocks are linked.
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+
*/
third->data = 3; // Assign data to the third block
third->next = NULL; // Pointer next to third block is null indicating that it is the last block
/* data has been assigned to the data part of the third block (block pointed by third).
And next pointer of the third block is made NULL to indicate that the linked list is
terminated here.
We have the linked list ready.
head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
*/
head = reverseList(head);
// Print the reversed linked list
Node *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
return 0;
}