![](/style/images/good.png)
![](/style/images/bad.png)
LeetCode: 707. Design Linked List
source link: https://mozillazg.com/2020/11/leetcode-707-design-linked-list.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目¶
原题地址: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)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK