题目¶
原题地址：https://leetcode.com/problems/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.
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.
Example 1:
Input ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] Output [null, null, null, null, 2, null, 3] Explanation MyLinkedList myLinkedList = new MyLinkedList(); 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
Constraints:
- 0 <= index, val <= 1000
- Please do not use the built-in LinkedList library.
- At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.
解法¶
使用单向链表实现¶
实现时主要需要注意处理几个边界 case:
- 当链表只有一个元素时，记得确保 head 和 tail 要指向同一个节点
- 当链表没有元素后，记得确保 head 和 tail 都没有指向任何节点
- 当删除 tail 指向的节点时，记得更新 tail 指向原来节点的上一个节点
这个方法的 Python 代码类似下面这样:
class Node(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList(object):
def __init__(self):
self._head = None
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
def addAtHead(self, 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
"""
node = Node(val, self._head)
self._head = node
self._length += 1
# 只有一个元素的链表 head 和 tail 指向同一个节点
if self._length == 1:
self._tail = self._head
def addAtTail(self, val):
"""
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:
self._head = self._tail
def addAtIndex(self, index, val):
"""
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:
self.addAtHead(val)
return
if index == self._length:
self.addAtTail(val)
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:
self._head = self._head.next
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:
self._tail = self._head = None
def _get_node_by_index(self, index):
node = self._head
curr_index = 0
while node is not None:
if curr_index == index:
return node
curr_index += 1
node = node.next
return None
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
Comments