Skip to content

Latest commit

 

History

History
198 lines (152 loc) · 4.2 KB

README.md

File metadata and controls

198 lines (152 loc) · 4.2 KB
Raw
comments difficulty edit_url tags
true
简单
数组
链表
双向链表

3263. 将双链表转换为数组 I 🔒

English Version

题目描述

给定一个 双链表 的 head 节点，其中的节点具有指向下一个节点的指针和上一个节点的指针。

返回一个 按顺序 包含链表中元素的整数数组。

 

示例 1：

输入：head = [1,2,3,4,3,2,1]

输出：[1,2,3,4,3,2,1]

示例 2：

输入：head = [2,2,2,2,2]

输出：[2,2,2,2,2]

示例 3：

输入：head = [3,2,3,2,3,2]

输出：[3,2,3,2,3,2]

 

提示：

  • 给定链表中节点的数量在 [1, 50] 范围。
  • 1 <= Node.val <= 50

解法

方法一：直接遍历

我们可以直接遍历链表，将节点的值依次添加到答案数组 $\textit{ans}$ 中。

遍历结束后，返回答案数组 $\textit{ans}$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为链表的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

Python3

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next
"""


class Solution:
    def toArray(self, root: "Optional[Node]") -> List[int]:
        ans = []
        while root:
            ans.append(root.val)
            root = root.next
        return ans

Java

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
};
*/

class Solution {
    public int[] toArray(Node head) {
        List<Integer> ans = new ArrayList<>();
        for (; head != null; head = head.next) {
            ans.add(head.val);
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }
}

C++

/**
 * Definition for doubly-linked list.
 * class Node {
 *     int val;
 *     Node* prev;
 *     Node* next;
 *     Node() : val(0), next(nullptr), prev(nullptr) {}
 *     Node(int x) : val(x), next(nullptr), prev(nullptr) {}
 *     Node(int x, Node *prev, Node *next) : val(x), next(next), prev(prev) {}
 * };
 */
class Solution {
public:
    vector<int> toArray(Node* head) {
        vector<int> ans;
        for (; head; head = head->next) {
            ans.push_back(head->val);
        }
        return ans;
    }
};

Go

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Prev *Node
 * }
 */

func toArray(head *Node) (ans []int) {
	for ; head != nil; head = head.Next {
		ans = append(ans, head.Val)
	}
	return
}

TypeScript

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     prev: _Node | null
 *     next: _Node | null
 *
 *     constructor(val?: number, prev? : _Node, next? : _Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.prev = (prev===undefined ? null : prev);
 *         this.next = (next===undefined ? null : next);
 *     }
 * }
 */

function toArray(head: _Node | null): number[] {
    const ans: number[] = [];
    for (; head; head = head.next) {
        ans.push(head.val);
    }
    return ans;
}