转变命运!揭秘反转链表的神奇算法!

简介: 转变命运!揭秘反转链表的神奇算法!


链表是计算机科学中常用的数据结构之一,它由一系列节点构成,每个节点包含一个值和指向下一个节点的指针。链表的灵活性使其在许多场景下被广泛应用,但其中的一个常见问题是如何反转链表。我们来了解下面两种实现链表反转的方法。

使用虚拟头节点来辅助实现链表反转

首先我们先来建立一个虚拟节点dummyNode,并且使dummyNode.next=head,这样就可以很好的简化我们的操作。

public ListNode reverseList(ListNode head) {
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = dummyNode.next;
            dummyNode.next = cur;
            cur = next;
        }
        return dummyNode.next;
    }

在循环体中,首先将cur.next赋值给next,用于保存cur的下一个节点。然后将dummyNode.next赋值给cur.next,即将cur与dummyNode相连,形成一个新的链表。接着将cur赋值给dummyNode.next,即将dummyNode与下一个节点相连。最后将next赋值给cur,继续遍历链表。

直接操作链表实现反转

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

方法内部定义了两个变量pre和cur,分别表示当前节点的前一个节点和当前节点。初始时,pre为null,cur为head。

接下来是一个while循环,当cur不为null时,循环继续执行。在循环内部,首先将cur的下一个节点赋值给next,然后将cur的next指针指向pre,即将当前节点cur与前一个节点pre相连。接着将pre赋值给cur,表示当前节点变为前一个节点。最后将next赋值给cur,表示将当前节点更新为下一个节点。

循环结束后,pre即为反转后的链表头节点,返回pre即可。

使用递归来实现链表反转

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
  1. 首先判断链表是否为空或只有一个节点,如果是,则直接返回head,因为不需要反转。
  2. 如果链表有多个节点,递归调用reverseList(head.next),将链表的剩余部分反转,并将新的头节点赋值给newHead。
  3. 接下来,将原链表的尾节点与新链表的头部相连,即将head.next.next指向head。
  4. 将原链表的尾节点置为null,表示已经处理完毕。
  5. 最后返回新的头节点newHead。

指定区间反转

指定区间反转我们有两种方法:头插法与穿针引线法。

我们以力扣92题做测试

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

头插法

具体思路就是在需要反转的区间内,每遍历一个节点,就让这个新节点来到反转的起始位置

public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) {
            return head;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next = null;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
  • 首先,如果链表为空(即head为null),则直接返回空链表。
  • 接下来,创建一个虚拟节点dummyNode,并将其next指针指向head。这样做的目的是为了方便处理边界情况,例如当left为1时,不需要对原始链表进行任何操作,直接返回dummyNode即可。
  • 然后,使用一个for循环遍历链表,找到第left个节点的前一个节点pre。接着,将cur指针指向pre的下一个节点,即第left个节点。
  • 接下来,使用另一个for循环遍历链表,从第left个节点开始,直到第right个节点。在每次循环中,首先将next指针指向cur的下一个节点,然后将cur的next指针指向next的下一个节点,将next的next指针指向pre的下一个节点,最后将pre的next指针指向next。这样就完成了链表中从第left个节点到第right个节点之间的节点反转操作。
  • 最后,返回dummyNode的next指针,即反转后的链表的头节点。

穿针引线法

大体思路就是确定好需要反转的部分,用一个反正链表的方法把需要反转的部分反转然后接回去。

public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        ListNode leftNode = pre.next;
        ListNode succ = rightNode.next;
        rightNode.next = null;
        reverse(leftNode);
        pre.next = rightNode;
        leftNode.next = succ;
        return dummyNode.next;
    }
    public void reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
  1. 创建一个虚拟头节点dummyNode,并将其next指向head。
  2. 创建一个指针pre,初始化为dummyNode。
  3. 遍历链表,找到第left-1个节点的前一个节点,将其赋值给pre。
  4. 找到第left个节点的前一个节点,将其赋值给rightNode。
  5. 找到第right个节点的下一个节点,将其赋值给leftNode。
  6. 找到第right+1个节点,将其赋值给succ。
  7. 将rightNode的next指针设为null,表示反转后的链表不包含第right个节点。
  8. 调用reverse方法,反转leftNode到rightNode之间的所有节点。
  9. 将pre的next指针指向rightNode,表示反转后的链表包含第left个节点和第right个节点。
  10. 将leftNode的next指针指向succ,表示反转后的链表包含第left+1个节点和第right+1个节点。
  11. 返回dummyNode的next指针,即反转后的链表的头节点。
目录
打赏
0
0
0
0
6
分享
相关文章
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
74 0
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
78 5
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
76 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
算法学习:数组 vs 链表
算法学习:数组 vs 链表
175 0
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
127 0
数据结构和算法学习记录——习题-移除链表元素
数据结构和算法学习记录——习题-移除链表元素
59 0
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
11月前
|
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
80 0
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
168 2

热门文章

最新文章

AI助理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问

你好,我是AI助理

可以解答问题、推荐解决方案等