leetcode 的单向链表与数组的转换

在 leetcode 的单向链表的题目中，通常会以数组的形式给出数据，导致我们在本地调试时，非常不方便。跟之前我们修改二叉树的样例一样：将 leetcode 中二叉树的数组结构转为真实的树结构。

这里我们写两个转换程序，实现单向链表和数组的双向转换。

在 C++ 的语言中，leetcode 官方给出的链表结构：

struct ListNode
{
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr)
    {
    }

    ListNode(int x) : val(x), next(nullptr)
    {
    }

    ListNode(int x, ListNode *next) : val(x), next(next)
    {
    }
};

1. 数组转单向链表 #

访问单向链表通常有循环和递归两种方式，这里转换时，我们也用两种方式来实现。

1.1 循环的方式 #

采用循环的方式，最需要注意的一点是头指针的处理，头指针的指向是不能跟着循环一起移动，需要单独处理。

/**
 * 数组转单向链表的循环方式
 * @param {vector<int>} nums 数组
 * @return {ListNode*} 构建的链表
 */
ListNode *vectorToListNode(vector<int> nums)
{
    if (nums.empty())
    {
        return nullptr;
    }
    auto head = new ListNode(nums[0]); // 头指针
    auto prev = head;
    for (int i = 1; i < nums.size(); i++) {
        auto node = new ListNode(nums[i]); // 创建一个新节点
        prev->next = node; // 上一个节点的next指向到当前节点
        prev = prev->next; // 将指针从上个节点移动到当前节点
    }
    return head;
}

1.2 递归的方式 #

使用递归的方式时，我这里传了一个下标过去，表示当前处理的是哪个节点。

/**
 * 数组转单向链表的递归方式
 * @param {vector<int>} nums 数组
 * @param {?int} index 数组的下标
 * @return {ListNode*} 构建的链表
 */
ListNode *vectorToListNode(vector<int> nums, int index = 0)
{
    if (index >= nums.size())
    {
        return nullptr;
    }

    auto node = new ListNode(nums[index]);
    // 递归下一个节点，并用next指向到下一个节点
    node->next = vectorToListNode(nums, index + 1);
    return node;
}

上面无论是哪种转换方式，使用方式都是一样的。

vector<int> nums = {1, 2, 3, 4, 5};
auto head = vectorToListNode(nums);
while (head) {
    cout << head->val << endl;
    head = head->next;
}

2. 单向链表转数组 #

链表转数组最简单的方式就是循环的方式了，直到链表的最后一个节点截止。

/**
 * 单向链表转数组
 * @param {ListNode*} head 链表的头指针
 * @return {vector<int>} 数组
 */
vector<int> ListNodeToVector(ListNode *head)
{
    vector<int> nums;

    while (head)
    {
        nums.push_back(head->val);
        head = head->next;
    }
    return nums;
}

3. 测试 #

我们可以在 leetcode 中选择一个题目来测试下：剑指 Offer 06. 从尾到头打印链表。