数据结构03：单链表逆置_单链表的逆置

单链表原地逆置

List Reverse(List L1){
    /*构造链表q替代L1（使得在逆置链表的时候L1本身不变）
     * 构造完以后q指向q链表末尾
     * 而指针p全程始终指向q链表的头结点
     * 从指针p（q链表头结点处）开始进行链表逆置
     * （实际上是把q链表逐个拆开组成逆置链表）：\
     * 设置指针prev置空
     * head = p->Next(第一个数据结点)
     * next = p->Next->Next(第二个数据结点)
     * 然后他俩逐个后推，将每次的head向后指向prev，prev也向前挪一位，
     * 实现prev始终指向逆置的链表第一个数据结点
     * 逆置结束之后再给prev添加一个头结点first，让L2指向first，返回L2即可完成
     * 此时：
     * q链表已经被拆成逆置链表了
     * L1不变（有头结点）
     * p只是指向原q链表的第一个头结点，
     * p->Next依然为原q链表第一个数据结点，
     * p->Next->Next = NULL(逆置的时候被拆了)
     * q依然指向原q链表的末尾，也就是逆置之后的第一个数据结点的位置
     * */
    List L2;
    List t = L1;
    List q = (List)malloc(sizeof(List));
    List p = q;
    t = t->Next;
    while(t != nullptr){
        PtrToNode s = (PtrToNode)malloc(sizeof(PtrToNode));
        s->Data = t->Data;
        q->Next = s;
        t = t->Next;
        if(t == nullptr){
            q = q->Next;
            q->Next = nullptr;
            break;
        }
        q = q->Next;
    }

    List prev = nullptr;
    List head = p->Next;
    List next = p->Next->Next;
    while(head != nullptr){
        head->Next = prev;
        prev = head;
        head = next;
        if(head == nullptr){
            break;
        }
        next = next->Next;
    }
    List first = (List)malloc(sizeof(List));
    first->Next = prev;
    L2 = first;
    return L2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

单链表利用栈逆置

List Reverse_stack(List L1){
    List L2 = (List)malloc(sizeof(PtrToNode));
    List L3 = L2;
    L1 = L1->Next;
    while(L1 != nullptr){
        List_stack.push(L1->Data);
        L1 = L1->Next;
    }
    const int List_stack_size = List_stack.size();
    for(int i = 0; i < List_stack_size; i++){
        PtrToNode s = (PtrToNode)malloc(sizeof(PtrToNode));
        s->Data = List_stack.top();
        L2->Next = s;
        L2 = L2->Next;
        List_stack.pop();
        if(List_stack.empty()){
            L2->Next = nullptr;
        }
    }
    return L3;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

.cpp文件

//
// Created by 15328 on 2022/1/24.
//
#include<bits/stdc++.h>
using namespace std;
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;
stack<ElementType> List_stack;
List Read(){
    List list = (List)malloc(sizeof(List));
    List p = list;
    int N;
    int value = 0;
    scanf("%d",&N);
    for(int i = 0; i < N; i++){
        PtrToNode s = (PtrToNode)malloc(sizeof(PtrToNode));
        scanf("%d",&value);
        s->Data = value;
        s->Next = nullptr;
        list->Next = s;
        list = list->Next;
    }
    return p;
}
void Print(List list){
    List p = list->Next;
    while(p != nullptr){
        printf("%d ",p->Data);
        p = p->Next;
    }
    printf("\n");
}
List Reverse(List L1){
    /*构造链表q替代L1（使得在逆置链表的时候L1本身不变）
     * 构造完以后q指向q链表末尾
     * 而指针p全程始终指向q链表的头结点
     * 从指针p（q链表头结点处）开始进行链表逆置
     * （实际上是把q链表逐个拆开组成逆置链表）：\
     * 设置指针prev置空
     * head = p->Next(第一个数据结点)
     * next = p->Next->Next(第二个数据结点)
     * 然后他俩逐个后推，将每次的head向后指向prev，prev也向前挪一位，
     * 实现prev始终指向逆置的链表第一个数据结点
     * 逆置结束之后再给prev添加一个头结点first，让L2指向first，返回L2即可完成
     * 此时：
     * q链表已经被拆成逆置链表了
     * L1不变（有头结点）
     * p只是指向原q链表的第一个头结点，
     * p->Next依然为原q链表第一个数据结点，
     * p->Next->Next = NULL(逆置的时候被拆了)
     * q依然指向原q链表的末尾，也就是逆置之后的第一个数据结点的位置
     * */
    List L2;
    List t = L1;
    List q = (List)malloc(sizeof(List));
    List p = q;
    t = t->Next;
    while(t != nullptr){
        PtrToNode s = (PtrToNode)malloc(sizeof(PtrToNode));
        s->Data = t->Data;
        q->Next = s;
        t = t->Next;
        if(t == nullptr){
            q = q->Next;
            q->Next = nullptr;
            break;
        }
        q = q->Next;
    }

    List prev = nullptr;
    List head = p->Next;
    List next = p->Next->Next;
    while(head != nullptr){
        head->Next = prev;
        prev = head;
        head = next;
        if(head == nullptr){
            break;
        }
        next = next->Next;
    }
    List first = (List)malloc(sizeof(List));
    first->Next = prev;
    L2 = first;
    return L2;
}

List Reverse_stack(List L1){
    List L2 = (List)malloc(sizeof(PtrToNode));
    List L3 = L2;
    L1 = L1->Next;
    while(L1 != nullptr){
        List_stack.push(L1->Data);
        L1 = L1->Next;
    }
    const int List_stack_size = List_stack.size();
    for(int i = 0; i < List_stack_size; i++){
        PtrToNode s = (PtrToNode)malloc(sizeof(PtrToNode));
        s->Data = List_stack.top();
        L2->Next = s;
        L2 = L2->Next;
        List_stack.pop();
        if(List_stack.empty()){
            L2->Next = nullptr;
        }
    }
    return L3;
}
int main()
{
    List L1, L2, L3;
    L1 = Read();
    L2 = Reverse(L1);
    L3 = Reverse_stack(L2);
    cout << "显示输入的单链表数据：";
    Print(L1);
    cout << "单链表原地逆置：\n先构造原链表的副本，然后从头逐个拆开这个副本，逐个逆置成逆序链表: \n";
    Print(L2);
    cout << "单链表利用栈逆置：\n把第一次逆置后的链表从头逐个压栈，再逐个弹出栈赋值给新逆置链表的结点\n";
    Print(L3);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

运行结果

E:\CODING__ALAN_CF\cmake-build-debug\Single_linkList_Reverse.exe
5
1 2 3 4 5
显示输入的单链表数据：1 2 3 4 5
单链表原地逆置：
先构造原链表的副本，然后从头逐个拆开这个副本，逐个逆置成逆序链表:
5 4 3 2 1
单链表利用栈逆置：
把第一次逆置后的从头逐个压栈，再逐个弹出栈赋值给新逆置链表的结点
1 2 3 4 5

进程已结束，退出代码为 0

1
2
3
4
5
6
7
8
9
10
11
12
13