题目链接

链表序列化

题目描述

你需要将一个单链表，按照从表头向表尾的顺序转化为一个序列（在 C++ 中是 vector，在 Java 中是 ArrayList，在 Python 中是 list）。

这是一个核心代码模式 (Core Code Mode) 的题目，你只需要实现 listnodeToVector 函数即可。

示例: 输入: {1,1,4,5,1,4}

输出: [1,1,4,5,1,4]

解题思路

这个问题本质上是要求我们遍历整个链表，并将每个节点的值依次存入一个动态数组中。这是一个非常直接和基础的链表操作。

算法步骤:

  1. 初始化:

    • 创建一个空的动态数组（如 C++ 的 std::vector<int>，Java 的 ArrayList<Integer> 或 Python 的 list）来存储结果。
    • 创建一个指针 current，并让它指向链表的头节点 head。

  2. 遍历:

    • 使用一个 while 循环，条件是 current 不为 nullptr (或 null/None)。这确保我们能访问到链中的每一个节点。
    • 在循环内部： a. 获取当前节点的值 current.val。 b. 将这个值添加到我们创建的动态数组的末尾。 c. 将 current 指针移动到下一个节点：current = current.next。

  3. 返回:

    • 当循环结束时，current 会是 nullptr，意味着我们已经遍历完了整个链表。
    • 此时，动态数组中已经按顺序包含了链表所有的节点值。我们只需返回这个数组即可。

这个算法能够优雅地处理空链表的情况：如果 head 一开始就是 null，循环条件不满足，函数会直接返回一个空数组，这是正确的行为。

代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return int整型vector
     */
    vector<int> listnodeToVector(ListNode* head) {
        vector<int> result;
        ListNode* current = head;
        while (current != nullptr) {
            result.push_back(current->val);
            current = current->next;
        }
        return result;
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> listnodeToVector(ListNode head) {
        ArrayList<Integer> result = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            result.add(current.val);
            current = current.next;
        }
        return result;
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return int整型一维数组
#
class Solution:
    def listnodeToVector(self, head: ListNode) -> List[int]:
        result = []
        current = head
        while current:
            result.append(current.val)
            current = current.next
        return result

算法及复杂度

  • 算法: 链表遍历
  • 时间复杂度: ，其中 是链表的节点数。因为我们需要访问每个节点一次。
  • 空间复杂度: 。我们需要一个大小为 的数组来存储链表的所有元素。这是返回值所必需的空间，不算作额外空间复杂度。如果题目要求计算额外空间，则为 （不计返回数组）。