Java数据结构 (链表反转（LinkedList----Leetcode206))

欢迎观看视频讲解反转链表原理（Java实现）_哔哩哔哩_bilibili-, 视频播放量 2、弹幕量 0、点赞数 1、投硬币枚数 0、收藏人数 1、转发人数 0, 视频作者 蝴蜨捷, 作者简介 ，相关视频：“蜗牛球”是如何制作的？把它放在斜坡上，有趣的现象发生了，铁路轨道原来是这样运作，兄弟俩买轨道玩具研究，终于搞懂了这个原理，常数背后的秘密，10秒钟教会你勾手发球的不同旋转原理，飞行原理最好的风洞教具，马士兵预测计算机行业未来3-5年内即将被淘汰的5种语言：Java、python、golang、C、C++、C#、前端、后端、大数据、AI、测试、运维、开发...，三年级上册期末成绩汇报！有惊无险！，如何在不可编程计算器上编写简单程序（整活版），为什么美国不敢直接禁止我国使用Windows系统？，你眼中的黑客技术VS实际上的黑客技术https://www.bilibili.com/video/BV1pqwaeREFL/?spm_id_from=333.1387.homepage.video_card.click&vd_source=a41a2b63314a64b2c32c7b595dedb2e4

1. 链表的当前结构

• 每个方框代表一个节点，每个节点包含两个部分：
  • 左侧的数字：节点存储的值，例如 45、34 等。
  • 右侧的地址（如 0x90）：表示该节点 next 指针指向的下一个节点的内存地址。
• 例子中，链表从右向左依次连接，形成 45 -> 34 -> 23 -> 12。

初始结构

• 链表的头节点为 12，head 指向 12。
• cur：当前节点，指向某个正在操作的节点。

2. 代码逻辑解读

head.next = null; // 第一步
cur.next = head;
head = cur;
cur = curN;

代码功能

1. head.next = null;

   • 将原链表的 head 的 next 置为 null，这是反转的关键一步，因为反转后，原来的头节点将变成尾节点。

2. cur.next = head;

   • 将当前节点 cur 的 next 指向 head。
   • 这样，当前节点 cur 插入到新链表的头部。

3. head = cur;

   • 更新头节点为 cur，当前节点变成了新链表的头部。

4. cur = curN;

   • 将 cur 更新为下一个节点 curN，继续处理链表的剩余部分。

---

3. 图示解析

• 初始状态：

• 完整代码:

  public ListNode reverseList(ListNode head) {
      ListNode cur = head;  // 当前节点
      ListNode curN;        // 下一个节点
      head = null;          // 初始化新链表的头部为空
      
      while (cur != null) {
          curN = cur.next;  // 保存下一个节点的位置
          cur.next = head;  // 当前节点指向新链表的头部
          head = cur;       // 更新新链表的头部
          cur = curN;       // 移动到下一个节点
      }
      return head;
  }
  

  5. 反转链表的特点

• 时间复杂度：O(n)，每个节点只处理一次。
• 空间复杂度：O(1)，只使用了固定的指针变量 cur 和 curN。
• 应用场景：
  • 需要逆序访问链表时（如回文检查）。
  • 数据倒序排列。

原文地址：https://blog.csdn.net/2301_80176774/article/details/145291150

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！