# LeetCode: 707. Design Linked List

## 题目¶

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

• 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.

Example 1:

Input
[[], [1], [3], [1, 2], [1], [1], [1]]

Output
[null, null, null, null, 2, null, 3]

Explanation

Constraints:

• 0 <= index, val <= 1000

## 解法¶

### 使用单向链表实现¶

• 当链表只有一个元素时，记得确保 head 和 tail 要指向同一个节点
• 当链表没有元素后，记得确保 head 和 tail 都没有指向任何节点
• 当删除 tail 指向的节点时，记得更新 tail 指向原来节点的上一个节点

class Node(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def __init__(self):
self._tail = None
self._length = 0

def get(self, index):
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
:type index: int
:rtype: int
"""
if index < 0 or index >= self._length:
return -1
node = self._get_node_by_index(index)
return node.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.
:type val: int
:rtype: None
"""
self._length += 1

# 只有一个元素的链表 head 和 tail 指向同一个节点
if self._length == 1:

"""
Append a node of value val to the last element of the linked list.
:type val: int
:rtype: None
"""
node = Node(val)
if self._tail is not None:
self._tail.next = node
self._tail = node
self._length += 1

# 只有一个元素的链表 head 和 tail 指向同一个节点
if self._length == 1:

"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
:type index: int
:type val: int
:rtype: None
"""
if index > self._length:
return
if index == 0:
return
if index == self._length:
return

pre = self._get_node_by_index(index -1)
curr = pre.next
node = Node(val, curr)
pre.next = node
self._length += 1

def deleteAtIndex(self, index):
"""
Delete the index-th node in the linked list, if the index is valid.
:type index: int
:rtype: None
"""
if index >= self._length:
return

if index == 0:
else:
pre = self._get_node_by_index(index -1)
curr = pre.next
pre.next = curr.next
# 删除 tail 指向的节点时更新新的 tail 指向节点
if index == self._length - 1:
self._tail = pre

self._length -= 1
# 当链表为空时 head 和 tail 不指向任何节点
if self._length == 0:

def _get_node_by_index(self, index):
curr_index = 0
while node is not None:
if curr_index == index:
return node
curr_index += 1
node = node.next

return None