{"id":3481,"date":"2018-08-09T00:33:13","date_gmt":"2018-08-09T07:33:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3481"},"modified":"2018-08-11T09:46:21","modified_gmt":"2018-08-11T16:46:21","slug":"leetcode-707-design-linked-list","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-707-design-linked-list\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 707. Design Linked List"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 707. Design Linked List - \u5237\u9898\u627e\u5de5\u4f5c EP216\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/dmezFFv522I?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>Problem<\/h1>\n<p>Design your\u00a0implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly\u00a0linked list should have two attributes:\u00a0<code>val<\/code>\u00a0and\u00a0<code>next<\/code>.\u00a0<code>val<\/code>\u00a0is the value of the current node, and\u00a0<code>next<\/code>\u00a0is\u00a0a\u00a0pointer\/reference to the next node. If you want to use the doubly linked list,\u00a0you will need\u00a0one more attribute\u00a0<code>prev<\/code>\u00a0to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.<\/p>\n<p>Implement these functions in your linked list class:<\/p>\n<ul>\n<li>get(index) : Get the value of\u00a0the\u00a0<code>index<\/code>-th\u00a0node in the linked list. If the index is invalid, return\u00a0<code>-1<\/code>.<\/li>\n<li>addAtHead(val) : Add a node of value\u00a0<code>val<\/code>\u00a0before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.<\/li>\n<li>addAtTail(val) : Append a node of value\u00a0<code>val<\/code>\u00a0to the last element of the linked list.<\/li>\n<li>addAtIndex(index, val) : Add a node of value\u00a0<code>val<\/code>\u00a0before the\u00a0<code>index<\/code>-th\u00a0node in the linked list.\u00a0If\u00a0<code>index<\/code>\u00a0equals\u00a0to the length of\u00a0linked 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.<\/li>\n<li>deleteAtIndex(index) : Delete\u00a0the\u00a0<code>index<\/code>-th\u00a0node in the linked list, if the index is valid.<\/li>\n<\/ul>\n<p><strong>Example:<\/strong><\/p>\n<pre class=\"lang:c++ decode:true \">MyLinkedList linkedList = new MyLinkedList();\r\nlinkedList.addAtHead(1);\r\nlinkedList.addAtTail(3);\r\nlinkedList.addAtIndex(1, 2);  \/\/ linked list becomes 1-&gt;2-&gt;3\r\nlinkedList.get(1);            \/\/ returns 2\r\nlinkedList.deleteAtIndex(1);  \/\/ now the linked list is 1-&gt;3\r\nlinkedList.get(1);            \/\/ returns 3\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li>All values will be in the range of\u00a0<code>[1, 1000]<\/code>.<\/li>\n<li>The number of operations will be in the range of\u00a0<code>[1, 1000]<\/code>.<\/li>\n<li>Please do not use the built-in LinkedList library.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3491\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3490\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3489\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3488\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-4.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/707-ep216-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution: Single linked list<\/strong><\/h1>\n<p>Keep tracking head and tail of the list.<\/p>\n<p>Time Complexity:<\/p>\n<p>addAtHead, addAtTail O(1)<\/p>\n<p>addAtIndex O(index)<\/p>\n<p>deleteAtIndex O(index)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>C++<\/p>\n<p>Tracking head\/tail and size of the list.<\/p>\n<pre class=\"height-set:true scroll:true lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 24 ms\r\nclass MyLinkedList {\r\npublic:\r\n  MyLinkedList(): head_(nullptr), tail_(nullptr), size_(0) {}\r\n  \r\n  ~MyLinkedList() {\r\n    Node* node = head_;\r\n    while (node) {\r\n      Node* cur = node;\r\n      node = node-&gt;next;\r\n      delete cur;\r\n    }\r\n    head_ = nullptr;\r\n    tail_ = nullptr;\r\n  }\r\n  \r\n  int get(int index) {\r\n    if (index &lt; 0 || index &gt;= size_) return -1;\r\n    auto node = head_;\r\n    while (index--)\r\n      node = node-&gt;next;    \r\n    return node-&gt;val;\r\n  }\r\n\r\n  void addAtHead(int val) {    \r\n    head_ = new Node(val, head_);\r\n    if (size_++ == 0)\r\n      tail_ = head_;   \r\n  }\r\n  \r\n  void addAtTail(int val) {\r\n    auto node = new Node(val);\r\n    if (size_++ == 0) {\r\n      head_ = tail_ = node;\r\n    } else {    \r\n      tail_-&gt;next = node;\r\n      tail_ = tail_-&gt;next;\r\n    }    \r\n  }\r\n\r\n  void addAtIndex(int index, int val) {\r\n    if (index &lt; 0 || index &gt; size_) return;\r\n    if (index == 0) return addAtHead(val);\r\n    if (index == size_) return addAtTail(val);\r\n    Node dummy(0, head_);\r\n    Node* prev = &amp;dummy;\r\n    while (index--) prev = prev-&gt;next;\r\n    prev-&gt;next = new Node(val, prev-&gt;next);    \r\n    ++size_;\r\n  }\r\n\r\n  void deleteAtIndex(int index) {\r\n    if (index &lt; 0 || index &gt;= size_) return;\r\n    Node dummy(0, head_);\r\n    Node* prev = &amp;dummy;\r\n    for (int i = 0; i &lt; index; ++i)\r\n      prev = prev-&gt;next;\r\n    Node* node_to_delete = prev-&gt;next;\r\n    prev-&gt;next = prev-&gt;next-&gt;next;\r\n    if (index == 0) head_ = prev-&gt;next;\r\n    if (index == size_ - 1) tail_ = prev;\r\n    delete node_to_delete;\r\n    --size_;\r\n  }\r\nprivate:\r\n  struct Node {\r\n    int val;\r\n    Node* next;\r\n    Node(int _val): Node(_val, nullptr) {}\r\n    Node(int _val, Node* _next): val(_val), next(_next) {}\r\n  };\r\n  Node* head_;\r\n  Node* tail_;\r\n  int size_;\r\n};\r\n<\/pre>\n<p>v2<\/p>\n<pre class=\"height-set:true scroll:true lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 28 ms\r\nclass MyLinkedList {\r\npublic:  \r\n  MyLinkedList(): head_(nullptr), tail_(nullptr), dummy_(0), size_(0) {}\r\n  \r\n  ~MyLinkedList() {\r\n    Node* node = head_;\r\n    while (node) {\r\n      Node* cur = node;\r\n      node = node-&gt;next;\r\n      delete cur;\r\n    }\r\n    head_ = nullptr;\r\n    tail_ = nullptr;\r\n  }\r\n  \r\n  int get(int index) {\r\n    if (index &lt; 0 || index &gt;= size_) return -1;\r\n    return getNode(index)-&gt;val;\r\n  }\r\n\r\n  void addAtHead(int val) {    \r\n    head_ = new Node(val, head_);\r\n    if (size_++ == 0)\r\n      tail_ = head_;   \r\n  }\r\n  \r\n  void addAtTail(int val) {\r\n    auto node = new Node(val);\r\n    if (size_++ == 0) {\r\n      head_ = tail_ = node;\r\n    } else {    \r\n      tail_-&gt;next = node;\r\n      tail_ = tail_-&gt;next;\r\n    }    \r\n  }\r\n\r\n  void addAtIndex(int index, int val) {\r\n    if (index &lt; 0 || index &gt; size_) return;\r\n    if (index == 0) return addAtHead(val);\r\n    if (index == size_) return addAtTail(val);\r\n    Node* prev = getNode(index - 1);\r\n    prev-&gt;next = new Node(val, prev-&gt;next);\r\n    ++size_;\r\n  }\r\n\r\n  void deleteAtIndex(int index) {\r\n    if (index &lt; 0 || index &gt;= size_) return;\r\n    Node* prev = getNode(index - 1);\r\n    Node* node_to_delete = prev-&gt;next;\r\n    prev-&gt;next = node_to_delete-&gt;next;\r\n    if (index == 0) head_ = prev-&gt;next;\r\n    if (index == size_ - 1) tail_ = prev;\r\n    delete node_to_delete;\r\n    --size_;\r\n  }\r\nprivate:\r\n  struct Node {\r\n    int val;\r\n    Node* next;\r\n    Node(int _val): Node(_val, nullptr) {}\r\n    Node(int _val, Node* _next): val(_val), next(_next) {}\r\n  };\r\n  \r\n  Node* head_; \/\/ Does not own\r\n  Node* tail_; \/\/ Does not own\r\n  Node dummy_;\r\n  int size_;\r\n  \r\n  Node* getNode(int index) {\r\n    dummy_.next = head_;\r\n    Node* n = &amp;dummy_;\r\n    for (int i = 0; i &lt;= index; ++i)\r\n      n = n-&gt;next;\r\n    return n;\r\n  }\r\n};<\/pre>\n<p>Python3<\/p>\n<pre class=\"height-set:true scroll:true lang:default decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 132 ms\r\n\"\"\"\r\nclass Node:\r\n  def __init__(self, val, _next=None):\r\n    self.val = val\r\n    self.next = _next\r\n    \r\nclass MyLinkedList:  \r\n  def __init__(self):\r\n    self.head = self.tail = None\r\n    self.size = 0\r\n  \r\n  def getNode(self, index):\r\n    n = Node(0, self.head)\r\n    for i in range(index + 1):\r\n      n = n.next\r\n    return n\r\n    \r\n  def get(self, index):\r\n    if index &lt; 0 or index &gt;= self.size: return -1\r\n    return self.getNode(index).val\r\n\r\n\r\n  def addAtHead(self, val):\r\n    n = Node(val, self.head)\r\n    self.head = n\r\n    if self.size == 0:\r\n      self.tail = n\r\n    self.size += 1\r\n\r\n\r\n  def addAtTail(self, val):\r\n    n = Node(val)\r\n    if self.size == 0:\r\n      self.head = self.tail = n\r\n    else:\r\n      self.tail.next = n\r\n      self.tail = n\r\n    self.size += 1\r\n\r\n  def addAtIndex(self, index, val):\r\n    if index &lt; 0 or index &gt; self.size: return\r\n    if index == 0: return self.addAtHead(val)\r\n    if index == self.size: return self.addAtTail(val)\r\n    prev = self.getNode(index - 1)\r\n    n = Node(val, prev.next)\r\n    prev.next = n\r\n    self.size += 1\r\n\r\n\r\n  def deleteAtIndex(self, index):\r\n    if index &lt; 0 or index &gt;= self.size: return\r\n    prev = self.getNode(index - 1)\r\n    prev.next = prev.next.next\r\n    if index == 0: self.head = prev.next\r\n    if index == self.size - 1: self.tail = prev\r\n    self.size -= 1<\/pre>\n<p>Java<\/p>\n<pre class=\"height-set:true lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 74 ms\r\nclass MyLinkedList {\r\n  class Node {\r\n    public int val;\r\n    public Node next;\r\n    public Node(int val) { this.val = val; this.next = null; }\r\n    public Node(int val, Node next) { this.val = val; this.next = next; }\r\n  }\r\n  \r\n  private Node head;\r\n  private Node tail;\r\n  private int size;\r\n  \r\n  public MyLinkedList() {\r\n    this.head = this.tail = null;\r\n    this.size = 0;\r\n  }\r\n  \r\n  private Node getNode(int index) {\r\n    Node n = new Node(0, this.head);\r\n    while (index-- &gt;= 0) {\r\n      n = n.next;\r\n    }\r\n    return n;\r\n  }\r\n\r\n  public int get(int index) {\r\n    if (index &lt; 0 || index &gt;= size) return -1;\r\n    return getNode(index).val;\r\n  }\r\n\r\n  public void addAtHead(int val) {\r\n    this.head = new Node(val, this.head);\r\n    if (this.size++ == 0)\r\n      this.tail = this.head;    \r\n  }\r\n\r\n  public void addAtTail(int val) {\r\n    Node n = new Node(val);\r\n    if (this.size++ == 0)\r\n      this.head = this.tail = n;\r\n    else\r\n      this.tail = this.tail.next = n;\r\n  }\r\n\r\n  public void addAtIndex(int index, int val) {\r\n    if (index &lt; 0 || index &gt; this.size) return;\r\n    if (index == 0)  { this.addAtHead(val); return; }\r\n    if (index == size) { this.addAtTail(val); return; }\r\n    Node prev = this.getNode(index - 1);\r\n    prev.next = new Node(val, prev.next);\r\n    ++this.size;\r\n  }\r\n\r\n  public void deleteAtIndex(int index) {\r\n    if (index &lt; 0 || index &gt;= this.size) return;\r\n    Node prev = this.getNode(index - 1);\r\n    prev.next = prev.next.next;\r\n    if (index == 0) this.head = prev.next;\r\n    if (index == this.size - 1) this.tail = prev;\r\n    --this.size;\r\n  }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Design your\u00a0implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[330,222,371,83],"class_list":["post-3481","post","type-post","status-publish","format-standard","hentry","category-list","tag-desgin","tag-easy","tag-implemenation","tag-list","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3481","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3481"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3481\/revisions"}],"predecessor-version":[{"id":3495,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3481\/revisions\/3495"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3481"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3481"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3481"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}