# LeetCode Medium 707. Design Linked List

tags: leetcode

インターンの応募ってこの時期多いのか中々返信が来ないですよね

待っている間に出来ることはたくさんあると思うんですが，私は待たされている状態にパフォーマンスが落ちるので出来ればあっちから連絡が欲しいですね(笑)←笑(笑)

問題

• Explore
• Problems

アイデア

連結リストを設計せよという問題です．

単方向でも双方向でもいいらしいので，ここでは簡単単方向を設計します．

• get(index):index目のノードを返す．なければ-1を返す．
• addAtHead(val): 先頭にvalを持つノードを付け，それを先頭とする．
• addAtTail(val): 末尾にvalを持つノードを付け，それを末尾とする．
• addAtIndex(index, val): index目のノードにvalを持つノードを付ける．
• deleteAtIndex(index): index目のノードを削除する

解法(doubly linked list)

実装するだけなのですが，その前に双方向なのでNodeのメンバー変数にはval，next，prevが必要です．

先頭を指すポインタheadだけでなく，末尾を指すポインタtailを使うことで計算量を落としています．

sizeによって処理を簡単にしています．

計算量

ノードの数を$N$とします．

• get(index)
  • 平均$O(N)$
• addAtHead(val)
  • $O(1)$
• addAtTail(val)
  • $O(1)$
• addAtIndex(index, val)
  • 平均$O(N)$
• deleteAtIndex(index)
  • 平均$O(N)$

C++

struct Node {
  int val;
  Node* next;
  Node* prev;
  Node(int x) : val(x), next(NULL), prev(NULL) {}
};
class MyLinkedList {
private:
  Node *head, *tail;
  int size;
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        head = NULL;
        tail = NULL;
        size = 0;
    }
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
      if (!head || index < 0 || size <= index)
        return -1;
      auto cur = head;
      for (int i = 0; i < index; ++i) {
        cur = cur->next;
      }
      return cur->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 addAtHead(int val) {
      auto newNode = new Node(val);
      newNode->next = head;
      if (head)
        head->prev = newNode;
      head = newNode;
      if (!tail)
        tail = head;
      ++size;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
      auto newNode = new Node(val);
      if (tail) {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
      } else {
        head = newNode;
        tail = newNode;
      }
      ++size;
    }
    
    /** 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. */
    void addAtIndex(int index, int val) {
      if (index <= size) {
        auto newNode = new Node(val);
        if (!head) {
          head = newNode;
          tail = newNode;
        } else {
          if (index == size) {
            auto cur = head;
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
          } else {
            auto cur = head;
            for (int i = 0; i < index; ++i)
              cur = cur->next;
            newNode->next = cur;
            newNode->prev = cur->prev;
            if (cur->prev)
              cur->prev->next = newNode;
            else
              head = newNode;
            cur->prev = newNode;
          }
        }
        ++size;
      }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
      if (head && 0 <= index && index < size) {
        auto cur = head;
        for (int i = 0; i < index; ++i)
          cur = cur->next;
        if (cur->prev) {
          if (cur->next) {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
          } else {
            cur->prev->next = NULL;
            tail = cur->prev;
          }
        } else {
          if (cur->next) {
            cur->next->prev = NULL;
            head = cur->next;
          } else {
            head = NULL;
            tail = NULL;
          }
        }
        --size;
      }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */