题解 | #序列链表化#

题目链接

题目描述

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

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

示例: 输入: [1,3,8]

输出: {1,3,8} (表示链表 1 -> 3 -> 8)

解题思路

将一个数组转换为链表，本质上是遍历数组，并为每个元素创建一个新的链表节点，然后将这些节点依次连接起来。为了方便地在链表末尾添加新节点，我们可以使用一个"尾指针"来追踪当前链表的最后一个节点。同时，使用一个"虚拟头节点"可以简化对链表头部的处理。

算法步骤:

处理边界情况:
- 如果输入的数组为空，那么应该返回一个空链表，即 nullptr (或 null/None)。
初始化:
- 创建一个虚拟头节点 dummy。这个节点本身不存储任何有效数据，它的 next 指针将指向我们构建的链表的真正头节点。
- 创建一个"尾指针" tail，并让它初始化时指向 dummy 节点。tail 将始终指向新建链表的最后一个节点。
遍历数组并构建链表:
- 遍历输入的数组中的每一个元素 value。
- 对于每一个 value： a. 创建一个新的链表节点 newNode，其值为 value。 b. 将当前链表的尾节点（tail）的 next 指针指向这个新创建的节点：tail->next = newNode。 c. 更新尾指针，使其指向新的尾节点：tail = tail->next (或者 tail = newNode)。
返回结果:
- 循环结束后，我们已经将数组中的所有元素都转换成了链表节点并正确连接。
- 真正的头节点是 dummy 节点的下一个节点。因此，返回 dummy->next。

这个方法使得每次添加新节点的操作都是 $\mathcal{O}(1)$ 的，因为我们不需要从头开始遍历链表来找到尾部。

代码

cpp
java
python

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int整型vector 
     * @return ListNode类
     */
    ListNode* vectorToListnode(vector<int>& arr) {
        if (arr.empty()) {
            return nullptr;
        }
        
        ListNode* dummy = new ListNode(0); // 虚拟头节点
        ListNode* tail = dummy;
        
        for (int val : arr) {
            tail->next = new ListNode(val);
            tail = tail->next;
        }
        
        ListNode* head = dummy->next;
        delete dummy;
        return head;
    }
};

/**
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param arr int整型一维数组 
     * @return ListNode类
     */
    public ListNode vectorToListnode(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        
        ListNode dummy = new ListNode(0); // 虚拟头节点
        ListNode tail = dummy;
        
        for (int val : arr) {
            tail.next = new ListNode(val);
            tail = tail.next;
        }
        
        return dummy.next;
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组
# @return ListNode类
#
class Solution:
    def vectorToListnode(self, arr: List[int]) -> ListNode:
        if not arr:
            return None
            
        dummy = ListNode(0) # 虚拟头节点
        tail = dummy
        
        for val in arr:
            tail.next = ListNode(val)
            tail = tail.next
            
        return dummy.next

算法及复杂度

算法: 迭代构建 (使用虚拟头节点和尾指针)
时间复杂度: $\mathcal{O}(N)$ ，其中 $N$ 是输入数组的长度。我们需要遍历数组一次。
空间复杂度: $\mathcal{O}(N)$ 。我们需要为数组中的每个元素创建一个新的 ListNode，这是返回值所必需的空间。