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

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。
• 应用场景：
  • 需要逆序访问链表时（如回文检查）。
  • 数据倒序排列。

反转链表原理（Java实现）_哔哩哔哩_bilibili