Hey, guys. I’m balls.

Today we are going to design linked lists and force you to understand the 5 operations of linked lists.

Set the bench and turn it on.

LeetCode 707: Design linked lists

The question

Implement linked list search, head insert method, tail insert method, universal insert, delete operation:

  • Get (index) : Gets the value of the index node in the list. If the index is invalid, -1 is returned.
  • AddAtHead (val) : Adds a node with the value val before the first element of the list. After insertion, the new node becomes the first node in the linked list.
  • AddAtTail (val) : Appends a node with the value val to the last element of the list.
  • AddAtIndex (index,val) : Adds a node with the value val before the index node in the linked list. If index is equal to the length of the list, the node is appended to the end of the list. If index is greater than the list length, no node will be inserted. If index is less than 0, insert the node in the header.
  • DeleteAtIndex (index) : Deletes the index of the list if the index index is valid.

The sample

prompt

  • 1 <= val <= 1000
  • 1 <= Number of operations <= 1000
  • You cannot use the built-in LinkedList library

title

Water problem, medium difficulty, examine the general operation of linked lists.

If you’re not familiar with linked lists, take a look at this article:

The illustration! Linked lists are really simple

If you look closely, there are five main operations involved in this problem:

  • Find the value of the index node in the list
  • Insert a node before the first node in the linked list
  • Insert a node after the last node in the linked list
  • Insert a node before the index node of the list
  • Deletes the index node of the linked list.

These 5 kinds of common add and delete operations include linked lists, which are perfect exercises for those who have just learned linked lists to consolidate their knowledge in time.

I’m going to do this with a singly linked list of leading nodes.

The head node, or what many might call the sentinel node, comes before the node of the first element, and the data field is generally meaningless.

The illustration

In order to facilitate subsequent operations, we usually define a simple node class first:

Initializes the head node and the length of the list in the list class.

Get (index), find the node, there is nothing to say, it is stupid to start from the first node to find. Time complexity O(n).

AddAtHead (val), insert a node in front of the first node in the list, good insert, just find the first node’s precursor node, here is the head node.

Because it’s the first one, it’s order one. List inserts must remember: the order of inserts cannot be changed! Remember that!

The successor pointer to the node to be inserted must point first, and then the precursor node to the node to be inserted.

In the figure below, the node with value 10 points to the node with value 11, and then the head node with value 0 points to the node with value 10.

Similarly, addAtTail(val) simply inserts a node after the last node in the list.

Because in the last one, the time complexity is order n.

AddAtIndex (index, val), insert a node before the index node of the list, in fact this is the general operation of insert. Search again from the first node in order, time complexity O(n).

AddAtHead (val) equals addAtIndex(0, val).

AddAtTail (val) is equivalent to addAtIndex(length, val).

DeleteAtIndex (index), delete the index node of the linked list, also find the precursor node to delete the node, by changing the node’s successor pointer to delete.

Similarly, the time to delete a linked list is O(n).

Code implementation

Class Node: def __init__(self, data): self. Val = data self. Next = None class MyLinkedList: def __init__(self): Self. Head = Node(0) # def get(self, index: 0) int) -> int: """ Get the value of the index-th node in the linked list. If the index is invalid, If index < 0 or index >= self.length: Return -1 p = self. Head i_index = 0 # range for _in range(index +1) : p = p.next return p.val def addAtHead(self, val: int) -> None: """ 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. """ return self.addAtIndex(0, val) def addAtTail(self, val: int) -> None: """ Append a node of value val to the last element of the linked list. """ return self.addAtIndex(self.length, val) def addAtIndex(self, index: int, val: int) -> None: """ 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, If index < 0: index = 0 if index > self.length: Return p = self.head add_node = Node(val) # for _ in range(val) : Self. length += 1 def deleteAtIndex(self, index: 0) def deleteAtIndex(self, index: 0) int) -> None: """ Delete the index-th node in the linked list, If index < 0 or index >=self.length: Return p = self.head # for _in range(index + 1): Next = p next = p next = p next Self. Length -= 1 # 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)Copy the code

Well, that’s the end of the graphic design list.

Foundation weak smelly treasure to think about this problem, want to understand, take the first step to learn the chain list.

After watching the true love, click the like message to this egg fly ~

I’m balls. I’ll see you next time!