1. Convert one of the arrays to a`set`. The elements are unique in a`set`.

2. When traversing the other array, ifthean element is found to already exist in the`set`, it means that the element belongs to the intersection, and the element should be added to the`results`.

2. When traversing the other array, if an element is found to already exist in the`set`, it means that the element belongs to the intersection, and the element should be added to the`results`.

3. The`results` is also of`set` type because duplicate removal is required.

Implement the`MyLinkedList` class:

*`MyLinkedList()` Initializes the`MyLinkedList` object.

*`int get(int index)` Get the value of the`index-th` node in the linked list. If the index is invalid, return`-1`.

*`void addAtHead(int val)` Add a node of value`val` before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

*`void addAtTail(int val)` Append a node of value`val` as the last element of the linked list.

*`void addAtIndex(int index, int val)` Add a node of value`val` before the`index-th` node in the linked list. If`index` equals the length of the linked list, the node will be appended to the end of the linked list. If`index` is greater than the length, the node will**not be inserted**.

*`void deleteAtIndex(int index)` Delete the`index-th` node in the linked list, if the index is valid.

-`MyLinkedList()` Initializes the`MyLinkedList` object.

-`int get(int index)` Get the value of the`index-th` node in the linked list. If the index is invalid, return`-1`.

-`void addAtHead(int val)` Add a node of value`val` before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

-`void addAtTail(int val)` Append a node of value`val` as the last element of the linked list.

-`void addAtIndex(int index, int val)` Add a node of value`val` before the`index-th` node in the linked list. If`index` equals the length of the linked list, the node will be appended to the end of the linked list. If`index` is greater than the length, the node will**not be inserted**.

-`void deleteAtIndex(int index)` Delete the`index-th` node in the linked list, if the index is valid.

**Input**

[中文题解](#中文题解)

实现`MyLinkedList` 类：

Implement the`MyLinkedList` class:

*`MyLinkedList()` Initializes the`MyLinkedList` object.

*`int get(int index)` Get the value of the`index-th` node in the linked list. If the index is invalid, return`-1`.

*`void addAtHead(int val)` Add a node of value`val` before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

*`void addAtTail(int val)` Append a node of value`val` as the last element of the linked list.

*`void addAtIndex(int index, int val)` Add a node of value`val` before the`index-th` node in the linked list. If`index` equals the length of the linked list, the node will be appended to the end of the linked list. If`index` is greater than the length, the node will**not be inserted**.

*`void deleteAtIndex(int index)` Delete the`index-th` node in the linked list, if the index is valid.

-`MyLinkedList()` 初始化`MyLinkedList` 对象。

-`int get(int index)` 获取链表中下标为`index` 的节点的值。如果下标无效，则返回`-1` 。

-`void addAtHead(int val)` 将一个值为`val` 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

-`void addAtTail(int val)` 将一个值为`val` 的节点追加到链表中作为链表的最后一个元素。

-`void addAtIndex(int index, int val)` 将一个值为`val` 的节点插入到链表中下标为`index` 的节点之前。如果`index` 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。

-`void deleteAtIndex(int index)` 如果下标有效，则删除链表中下标为`index` 的节点。

**Input**

MyLinkedList myLinkedList=newMyLinkedList();

myLinkedList.addAtHead(1);

myLinkedList.addAtTail(3);

myLinkedList.addAtIndex(1,2);//linked list becomes 1->2->3

myLinkedList.get(1);//return 2

myLinkedList.deleteAtIndex(1);//now the linked list is 1->3

myLinkedList.get(1);//return 3

myLinkedList.addAtIndex(1,2);//链表变为 1->2->3

myLinkedList.get(1);//返回 2

myLinkedList.deleteAtIndex(1);//现在，链表变为 1->3

myLinkedList.get(1);//返回 3

-Please do not use the built-inLinkedListlibrary.

-请不要使用内置的LinkedList库。

Before solving this problem, it is recommended to solve the simple problem[19. Remove Nth Node From End of List](19-remove-nth-node-from-end-of-list.md) first.