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

蚊子前端博客
发布于 2022-06-21 10:55
leetcode中如何将单向链表与数组进行转换?

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

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

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

COPYCPP

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 循环的方式

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

COPYCPP

/** * 数组转单向链表的循环方式 * @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 递归的方式

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

COPYCPP

/** * 数组转单向链表的递归方式 * @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; }

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

COPYCPP

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

2. 单向链表转数组

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

COPYCPP

/** * 单向链表转数组 * @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. 从尾到头打印链表

标签:
阅读(325)

公众号:

qrcode

微信公众号:前端小茶馆