03.1 单链表反转

moye Lv6
  2024-07-18 14:30:25 2024-07-18 14:30:25 创建   2025-12-11 14:39:48 2025-12-11 14:39:48 更新      

单链表反转：改变链的方向

单链表反转是一种常见而重要的链表操作，它可以改变链表的方向，使得原先的尾节点成为新的头节点。

1. 单链表反转的基本原理

单链表反转的核心思想是通过改变节点之间的链接方向，将链表的尾部连接到头部。这个操作可以通过遍历链表并逐个调整节点的 next 指针来实现。

2. Python单链表反转的实现方式

2.1 迭代法

迭代法是一种直观而简单的实现方式，通过遍历链表，逐个改变节点的 next 指针方向。以下是一个使用迭代法的示例（使用Python）：

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
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

# 示例使用
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head = reverse_linked_list(head)

# 输出反转后的链表
current = reversed_head
while current is not None:
    print(current.value, end=" -> ")
    current = current.next
print("None")

2.2 递归法

递归法是一种更为巧妙的实现方式，通过递归地反转子链表，并调整当前节点的指针。以下是一个使用递归法的示例（使用Python）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def reverse_linked_list_recursive(head):
    if head is None or head.next is None:
        return head

    new_head = reverse_linked_list_recursive(head.next)
    head.next.next = head
    head.next = None

    return new_head

# 示例使用
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head_recursive = reverse_linked_list_recursive(head)

# 输出递归反转后的链表
current = reversed_head_recursive
while current is not None:
    print(current.value, end=" -> ")
    current = current.next
print("None")

3. Java单链表反转的实现方式

实现思路：

  1. 先定义一个节点 reverseHead = new HeroNode();
  2. 从头到尾遍历，每遍历一个节点就将其取出并放在新链表的最前端
  3. 原来的链表head.next = reverseHead.next
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
package org.example;  
  
import static org.example.SinglelinkedList.*;  
  
public class SingleLinkedListDemo {  
    public static void main(String[] args) {  
        HeroNode heroNode1 = new HeroNode(1, "一号", "1号");  
  
        HeroNode heroNode2 = new HeroNode(2, "二号", "2号");  
  
        HeroNode heroNode3 = new HeroNode(3, "三号", "3号");  
  
        HeroNode heroNode4 = new HeroNode(4, "四号", "4号");  
  
        HeroNode heroNode5 = new HeroNode(4, "五号", "5号");  
  
        HeroNode heroNode6 = new HeroNode(6, "六号", "6号");  
  
//        创建链表  
        SinglelinkedList singlelinkedList = new SinglelinkedList();  
//        加入  
        singlelinkedList.add(heroNode1);  
        singlelinkedList.add(heroNode2);  
        singlelinkedList.add(heroNode3);  
        singlelinkedList.add(heroNode4);  
  
        singlelinkedList.list();  
        singlelinkedList.del(heroNode3);  
        singlelinkedList.list();  
        System.out.println("有效的节点个数：" + getLength(singlelinkedList.getHead()));  
  
        singlelinkedList.addByOrder(heroNode5);  
        singlelinkedList.addByOrder(heroNode6);  
        singlelinkedList.addByOrder(heroNode3);  
        singlelinkedList.list();  
  
//        HeroNode res = findLastIndexNode(singlelinkedList.getHead(), 2);  
//        System.out.println(res);  
        System.out.println("反转单链表-------");  
        reverseList(singlelinkedList.getHead());  
        singlelinkedList.list();  
    }  
}  
  
//定义SingleLinkedList来管理角色  
class SinglelinkedList {  
  
    //返回头节点  
    public HeroNode getHead() {  
        return head;  
    }  
  
    //    初始化头节点，不动头节点  
    private HeroNode head = new HeroNode(0, "", "");  
  
    public void add(HeroNode heroNode) {  
        //    添加节点搭配单向链表  
        //    思路：不考虑编号顺序时，  
        //    找到当前链表的最后节点，并将其next指向新的节点  
        HeroNode temp = head;  
//        遍历链表，找到最后一个  
        while (true) {//退出循环时，temp指向最后  
            if (temp.next == null) {  
                break;  
            }  
            temp = temp.next;  
        }  
        temp.next = heroNode;  
    }  
  
    public void addByOrder(HeroNode heroNode) {  
        HeroNode temp = head;  
//        temp位于添加的前一个节点  
        boolean flag = false;//添加的编号是否存在  
        while (true) {  
            if (temp.next == null) {//处在链表最后  
                break;  
            }  
            if (temp.next.no > heroNode.no) {//位置找到了  
                break;  
            } else if (temp.next.no == heroNode.no) {  
                flag = true;//说明编号存在  
                break;  
            }  
            temp = temp.next;  
        }  
//        判断flag  
        if (flag) {  
            System.out.println("准备插入的编号已经存在,不能加入");  
        } else {  
            //添加到链表中  
            heroNode.next = temp.next;  
            temp.next = heroNode;  
        }  
    }  
  
    //    根据no修改节点的信息  
    public void update(HeroNode heroNode) {  
//        判断是否为空  
        if (heroNode.next == null) {  
            System.out.println("链表为空");  
            return;  
        }  
        //找到需要修改的节点,根据no修改.遍历  
        HeroNode temp = head.next;  
        boolean flag = false;  
        while (true) {  
            if (temp.next == null) {  
                break;  
            }  
            if (temp.no == heroNode.no) {  
                flag = true;  
                break;  
            }  
            temp = temp.next;  
        }  
        if (flag) {  
            temp.nickname = heroNode.nickname;  
            temp.name = heroNode.name;  
        } else {  
            System.out.println("未找到编号");  
        }  
    }  
  
    public void del(HeroNode heroNode) {  
        //        判断是否为空  
        if (heroNode.next == null) {  
            System.out.println("链表为空");  
            return;  
        }  
        HeroNode temp = head.next;  
        boolean flag = false;  
        while (true) {  
            if (temp.next == null) {  
                break;  
            }  
            if (temp.next.no == heroNode.no) {  
                flag = true;  
                break;  
            }  
            temp = temp.next;  
        }  
        if (flag) {  
            temp.next = temp.next.next;  
        } else {  
            System.out.println("要删除的不存在");  
        }  
    }  
  
    /**  
     * @param head 链表头节点  
     * @return 返回有效节点的个数  
     */  
    //获取单链表有效节点的个数（带头节点需要不统计头节点）  
    public static int getLength(HeroNode head) {  
        if (head.next == null) {  
            return 0;  
        }  
        int length = 0;  
  
//        定义辅助节点，不统计头节点  
        HeroNode cur = head.next;  
        while (cur != null) {  
            length++;  
            cur = cur.next;  
        }  
        return length;  
    }  
  
    //查找单链表的倒数第k个节点\  
//    1.编写方法接受head节点，同时接收index表示倒数第index个节点  
//    2.先把链表从头到尾遍历，length-index  
    public static HeroNode findLastIndexNode(HeroNode head, int index) {  
        if (head.next == null) {  
            return null;  
        }  
//        第一次遍历，得到链表长度  
        int length = getLength(head);  
//        第二次遍历length-index  
        if (index <= 0 || index > length) {  
            return null;  
        }  
        HeroNode temp = head.next;  
        for (int i = 0; i < length - index; i++) {  
            temp = temp.next;  
        }  
        return temp;  
    }  
  
    public static void reverseList(HeroNode head) {  
        if (head.next == null || head.next.next == null) {  
            return;  
        }  
        HeroNode cur = head.next;  
        HeroNode next = null;  
        HeroNode reverseHead = new HeroNode(0, "", "");  
//        遍历原来的链表  
        while (cur != null) {  
            next = cur.next;  
            cur.next = reverseHead.next;  
            reverseHead.next = cur;  
            cur = next;  
        }  
        head.next = reverseHead.next;  
    }  
  
    //    显示链表  
    public void list() {  
//        先判断链表是否为空  
        if (head.next == null) {  
            System.out.println("链表为空");  
            return;  
        }  
//        因为头节点不能动，因此需要辅助变量进行遍历  
        HeroNode temp = head.next;  
        while (true) {  
            if (temp == null) {  
                return;  
            }  
//            输出节点信息|  
            System.out.println(temp);  
//            temp后移  
            temp = temp.next;  
        }  
    }  
}  
  
  
//定义HeroNode,每个HeroNode对象就是一个节点  
class HeroNode {  
    public int no;  
    public String name;  
    public String nickname;  
    public HeroNode next;  
  
    //    构造器  
    public HeroNode(int no, String name, String nickname) {  
        this.name = name;  
        this.no = no;  
        this.nickname = nickname;  
    }  
  
    @Override  
    public String toString() {  
        return "HeroNode{" +  
                "no=" + no +  
                ", name='" + name + '\'' +  
                ", nickname='" + nickname + '\'' +  
                '}';  
    }  
}

4. 单链表反转的应用场景

4.1 数据库查询结果

在数据库查询结果返回时，常常使用链表结构，而在前端或后端中，可能需要反转链表以满足特定需求。

4.2 链表栈

在实现链表栈时，有时需要将栈的顺序反转，以便于一些特定操作。

5. 总结

单链表反转是一种常见而基础的链表操作，通过改变节点之间的链接方向，使得链表的尾部变为新的头部。实现方式有迭代法和递归法，各有特点。

  • 标题: 03.1 单链表反转
  • 作者: moye
  • 创建于 : 2024-07-18 14:30:25
  • 更新于 : 2025-12-11 14:39:48
  • 链接: https://www.kanes.top/2024/07/18/03.1 单链表反转/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
03.1 单链表反转
  1. 1. 单链表反转：改变链的方向
    1. 1.1. 1. 单链表反转的基本原理
    2. 1.2. 2. Python单链表反转的实现方式
      1. 1.2.1. 2.1 迭代法
      2. 1.2.2. 2.2 递归法
    3. 1.3. 3. Java单链表反转的实现方式
    4. 1.4. 4. 单链表反转的应用场景
      1. 1.4.1. 4.1 数据库查询结果
      2. 1.4.2. 4.2 链表栈
    5. 1.5. 5. 总结