剑指 Offer 06. 从尾到头打印链表（Easy）

题目描述

• 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
• 限制：0 <= 链表长度 <= 10000。

举例说明

• 示例 1：
  • 输入：head = [1,3,2]。
  • 输出：[2,3,1]。

解题思路

• 利用递归：先走至链表末端，回溯时依次将节点值加入列表，这样就可以实现链表值的倒序输出。
• 算法流程：
  • 递推阶段：每次传入 head.next，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
  • 回溯阶段：层层回溯时，将当前节点值加入列表，即 temp.add(head.val)。
  • 最终，将列表 temp 转化为数组 res ，并返回即可。
• 代码示例：

  class Solution {
      List<Integer> temp = new ArrayList<Integer>();
      public int[] reversePrint(ListNode head) {
          reverse(head);
          int[] res = new int[temp.size()];
          for (int i = 0; i < res.length; i++) {
              res[i] = temp.get(i);
          }
          return res;
      }
  
      private void reverse(ListNode head) {
          if (head == null) {
              return;
          }
          reverse(head.next);
          temp.add(head.val);
      }
  }
  

• 复杂度分析：
  • 时间复杂度 O(N)： 遍历链表，递归 N 次。
  • 空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。

剑指 Offer 24. 反转链表（Easy）

题目描述

• 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
• 限制：0 <= 节点个数 <= 5000。

举例说明

• 示例：
  • 输入: 1->2->3->4->5->NULL。
  • 输出: 5->4->3->2->1->NULL。

解题思路

• 算法流程：
  • 定义两个指针：pre 和 cur。
  • pre 在前 cur 在后。
  • 每次让 pre 的 next 指向 cur，实现一次局部反转。
  • 局部反转完成之后，pre 和 cur 同时往前移动一个位置。
  • 循环上述过程，直至 pre 到达链表尾部。
• 代码示例：

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

• 复杂度分析：
  • 时间复杂度 O(N)： 遍历链表使用线性大小时间。
  • 空间复杂度 O(1)： 变量 pre 和 cur 使用常数大小额外空间。

剑指 Offer 35. 复杂链表的复制（Medium）

题目描述

• 请实现 copyRandomList 函数，复制一个复杂链表。
• 在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
• 限制：
  • -10000 <= Node.val <= 10000。
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000。

举例说明

• 示例 1：
  
  • 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]。
  • 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]。
• 示例 2：
  
  • 输入：head = [[1,1],[2,1]]。
  • 输出：[[1,1],[2,1]]。
• 示例 3：
  
  • 输入：head = [[3,null],[3,0],[3,null]]。
  • 输出：[[3,null],[3,0],[3,null]]。
• 示例 4：
  • 输入：head = []。
  • 输出：[]。
  • 解释：给定的链表为空（空指针），因此返回 null。

解题思路

• 利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。
• 算法流程：
  • 若头节点 head 为空节点，直接返回 null；
  • 初始化：哈希表 map，节点 cur 指向头节点；
  • 复制链表：
    • 建立新节点，并向 map 添加键值对 (原 cur 节点, 新 cur 节点）；
    • cur 遍历至原链表下一节点；
  • 构建新链表的引用指向：
    • 构建新节点的 next 和 random 引用指向；
    • cur 遍历至原链表下一节点；
  • 返回值：新链表的头节点 map[head]；
• 代码示例：

  class Solution {
      public Node copyRandomList(Node head) {
          Map<Node, Node> map = new HashMap<>();
          Node cur = head;
  
          while (cur != null) {
              if (!map.containsKey(cur)) {
                  map.put(cur, new Node(cur.val));
              }
              cur = cur.next;
          }
  
          cur = head;
          while (cur != null) {
              if (cur.next != null) {
                  map.get(cur).next = map.get(cur.next);
              }
              if (cur.random != null) {
                  map.get(cur).random = map.get(cur.random);
              }
              cur = cur.next;
          }
  
          return map.get(head); 
      }
  }
  

• 复杂度分析：
  • 时间复杂度 O(N)：两轮遍历链表，使用 O(N) 时间。
  • 空间复杂度 O(N)： 哈希表 map 使用线性大小的额外空间。