Skip to content

Latest commit

 

History

History
205 lines (162 loc) · 4.51 KB

README.md

File metadata and controls

205 lines (162 loc) · 4.51 KB
Raw
comments difficulty edit_url tags
true
中等
数组
链表
双向链表

3294. 将双链表转换为数组 II 🔒

English Version

题目描述

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

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

 

示例 1：

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

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

示例 2：

输入：head = [4,5,6,7,8], node = 8

输出：[4,5,6,7,8]

 

提示：

  • 给定列表中的节点数在范围 [1, 500] 内。
  • 1 <= Node.val <= 1000
  • 所有节点的 Node.val 互不相同。

解法

方法一：遍历链表

我们可以从给定的节点开始，往前遍历链表，直到遍历到头节点，然后再从头节点开始往后遍历链表，将遍历到的节点的值添加到答案数组中。

遍历结束后，返回答案数组即可。

时间复杂度 $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, node: "Optional[Node]") -> List[int]:
        while node.prev:
            node = node.prev
        ans = []
        while node:
            ans.append(node.val)
            node = node.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 node) {
        while (node != null && node.prev != null) {
            node = node.prev;
        }
        var ans = new ArrayList<Integer>();
        for (; node != null; node = node.next) {
            ans.add(node.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* node) {
        while (node && node->prev) {
            node = node->prev;
        }
        vector<int> ans;
        for (; node; node = node->next) {
            ans.push_back(node->val);
        }
        return ans;
    }
};

Go

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

func toArray(node *Node) (ans []int) {
	for node != nil && node.Prev != nil {
		node = node.Prev
	}
	for ; node != nil; node = node.Next {
		ans = append(ans, node.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(node: _Node | null): number[] {
    while (node && node.prev) {
        node = node.prev;
    }
    const ans: number[] = [];
    for (; node; node = node.next) {
        ans.push(node.val);
    }
    return ans;
}