算法:单链表反转

2023-12-14 11:57:26

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

一、问题描述

二、栈解法Stack

三、三指针法

总结


提示:以下是本篇文章正文内容,下面案例可供参考

一、问题描述

有个单链表,现要将其反转

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

二、栈解法Stack

解题思路:

栈的特点,先进后出,我们可以将链表节点入栈,然后再出栈,将出栈的元素连在一起,就是反转之后的单链表了。

代码示例:

三、三指针法

解题思路:

需要三个指针,分别指向当前、前一个、后一个节点,每断开一段关系,得记录下来关系的前后节点,然后这三个指针同步向后移动

代码示例:

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

关键代码如上,next记录的永远是下一个节点,head记录的是当前节点,pre记录的是上一个节点,可以假设头节点前还有一个null节点?

理解这个代码有点儿绕,画个图看看

初始状态:

第一次演进:

第二次演进:

此时,head和next都指向null,pre指向了最后一个节点B,跳出while循环

最后把pre赋值给head,就完成了单链表的反转,由A指向B,变为B指向A。


总结

换一种思路,豁然开朗,多动手,简单到有手就行!

文章来源:https://blog.csdn.net/ql_gome/article/details/134978941
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。