1
//
2
// Created by Rock Zhang on 2025/9/22.
3
//
4
#include <stdio.h>
5
#include <stdlib.h>
6

7
typedef struct {
8
    int data;
9
    struct Node* next; //指向同一类型(struct Node)结构体的指针
10
} Node;
11

12
typedef struct {
13
    Node* head;
14
    int length;
15
} LinkedList;
16

17
void initList(LinkedList*  list)
18
{
19
    list -> head = NULL;
20
    list -> length = 0;
21
}
22

23
void insert(LinkedList* list, int data)
24
{
25
    Node* newnode = (Node*)malloc(sizeof(Node));
26
    newnode -> data = data;
27
    newnode -> next = list -> head;  // 新节点就连接到了链表的现有部分之前
28
    list -> head = newnode;  // 新节点成为了链表的新头部
29
    list -> length++;
30
}
31

32
void append(LinkedList* list, int data)
33
{
34
    Node* newnode = (Node*)malloc(sizeof(Node));
35
    newnode -> data = data;
36
    newnode -> next = NULL;
37
    if (list -> head == NULL)
38
    {
39
        list -> head = newnode;
40
    }
41
    else
42
    {
43
        Node* current = list -> head;
44
        while (current -> next != NULL)
45
        {
46
            current = current -> next;
47
        }
48
        current -> next = newnode;
49
    }
50
}
51

52
int search(LinkedList* list, int data)
53
{
54
    Node* current = list -> head;
55
    int index = 0;
56
    while (current != NULL)
57
    {
58
        if (current -> data == data)
59
        {
60
            printf("你搜索的数 %d 的索引是 %d\n", data, index);
61
        }
62
        current = current -> next;
63
        index++;
64
    }
65
    return -1;
66
}
67

68
void reverse(LinkedList* list)
69
{
70
    if (list->head == NULL || list->head->next == NULL) {
71
        // 如果链表为空或只有一个节点，无需反转，直接返回
72
        return;
73
    }
74
    Node* prev_node = NULL;      // 指向前一个节点
75
    Node* current = list->head; // 指向当前节点
76
    Node* next_node = NULL;     // 临时指针，用于保存下一个节点
77
    // 遍历链表
78
    while (current != NULL) {
79
        // 1. 保存当前节点的下一个节点
80
        next_node = current->next;
81

82
        // 2. 将当前节点的next指针指向前一个节点（实现反转）
83
        current->next = prev_node;
84

85
        // 3. prev和current指针向后移动，为下一次反转做准备
86
        prev_node = current;
87
        current = next_node;
88
    }
89
    // 循环结束后，prev指向原链表的最后一个节点，即新链表的头节点
90
    list->head = prev_node;
91
}
92

93
void printList(LinkedList* list)
94
{
95
    Node* current = list -> head;
96
    while (current != NULL)
97
    {
98
        printf("%d ", current -> data);
99
        current = current -> next;
100
    }
101
    printf("\n");
102
}
103

104
int main()
105
{
106
    LinkedList list;
107
    initList(&list);
108
    insert(&list, 2);
109
    insert(&list, 1);
110
    append(&list, 5);
111
    insert(&list, 3);
112
    insert(&list, 5);
113
    append(&list, 4);
114
    printList(&list);
115
    reverse(&list);
116
    search(&list, 5);
117
    return 0;
118
}