Aaron Teo

← Back to home

[LeetCode 707] [Medium] Design Linked List

Question

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.

  • MyLinkedList() Initializes the MyLinkedList object.
  • int get(int index) Get the value of the indexth 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 indexth 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 indexth node in the linked list, if the index is valid.

Example:

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

Solution

Create a Doubly ListNode object that holds the three attributes, val, prev and next. Next, instantiate two dummy nodes to cover the top and tail ends of the linked list.

Next we will implement the following logic for the different functions that are required for the linked list object. Define a new function, addNewNodeBeforeCurrentNode that will be reused by the different methods that are required to add a new node before the current node.

  • get(self, index): Using the index, traverse through the current linked list, while the current node is not None, and index is greater than 0, we will continue to move to the next node, and decrement the index. At the end of the loop, if the current node is not None and it is not the tail dummy node, and the index is 0 (i.e. which means that the index is not out of bounds), we will return the current node's value.
  • addAtHead(self, val): Create a new ListNode which with the new value, and then utilise the function, addNewNodeBeforeCurrentNode to append the node to the actual head of the linked list (i.e. the node after the dummy head node).
  • addAtTail(self, val): Create a new ListNode which with the new value, and then utilise the function, addNewNodeBeforeCurrentNode to append the node to the tail dummy node (i.e. which is the position that is after the actual tail node that you would like to insert to)
  • addAtIndex(self, index, val): Using the index, traverse through each and every node, after the traversal loop, if the current last visited position is not None, and the index is 0, we will create a new node with the new value, and then append it to the last visited node using the function, addNewNodeBeforeCurrentNode
  • deleteAtIndex(self, index): Using the index, traverse to the node that you would like to remove from the linked list. After the traversal, if the last visited node is not None, and it is not the last dummy node in the linked list, and index is 0, we will remove the node, by reassigning the next and prev references from the previous and next nodes from the current last visited node.

Code

# Definition for doubly-linked list.
class ListNode(object):
    def __init__(self, val=0):
        self.val = val
        self.next = None
        self.prev = None

class MyLinkedList(object):

    def __init__(self):
        # create a dummy nodes on each end
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def addNewNodeBeforeCurrentNode(self, currNode, PrevNode, newNode):
        PrevNode.next = newNode
        currNode.prev = newNode
        newNode.next = currNode
        newNode.prev = PrevNode

    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        curr = self.head.next
        while curr and index > 0:
            curr = curr.next
            index -= 1
        
        if curr and curr != self.tail and index == 0:
            return curr.val
        
        return -1

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """

        newNode = ListNode(val)
        currentNodeToAddBefore = self.head.next
        prevNode = self.head
        self.addNewNodeBeforeCurrentNode(currentNodeToAddBefore, prevNode, newNode)

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        newNode = ListNode(val)
        currentNodeToAddBefore = self.tail
        prevNode = self.tail.prev
        self.addNewNodeBeforeCurrentNode(currentNodeToAddBefore, prevNode, newNode)
        
    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """

        curr = self.head.next
        while curr and index > 0:
            index -= 1
            curr = curr.next
        if curr and index == 0:
            newNode = ListNode(val)
            currentNodeToAddBefore = curr
            prevNode = curr.prev
            self.addNewNodeBeforeCurrentNode(currentNodeToAddBefore, prevNode, newNode)


    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        curr = self.head.next
        while curr and index > 0:
            index -= 1
            curr = curr.next
        
        if curr and curr != self.tail and index == 0:
            originalNextNode = curr.next
            originalPrevNode = curr.prev
            originalPrevNode.next = originalNextNode
            originalNextNode.prev = originalPrevNode


# 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)
← Back to home