707. Design Linked List - 연결리스트 기본 구현 문제

https://leetcode.com/problems/design-linked-list/

Design Linked List - LeetCode

 

말 그대로 단순 연결 리스트를 구현하는 문제.

중간 중간에 처리해야할 경우의 수도 많아서, 애를 먹었다. 이 코드는 더미 노드를 쓰지는 않았는데, 추후 더미 노드를 사용하는 방법 또한 고려해봐야 할 듯?

 

struct Node {
    int val;
    Node *next;
    Node () : val(), next(nullptr) {}
    Node(int x) : val(x), next(nullptr) {}
};

class MyLinkedList
{
private:
    Node *head;
    Node *tail;
    int length;
    
public:
  /** Initialize your data structure here. */
  MyLinkedList()
  {
    head = nullptr;
    tail = nullptr;
    
    length = 0;
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  int get(int index)
  {
    Node *cur = head;

    if (length <= index)
      return -1;

    for (int i = 0; index > i; 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)
  {
    Node *newNode = new Node(val);

    newNode->next = head;
    head = newNode;
     
    if (length == 0)  
        tail = head;
    length++;
      
  }

  /** Append a node of value val to the last element of the linked list. */
  void addAtTail(int val)
  {
    Node *newNode = new Node(val);

    if (tail != nullptr)
        tail->next = newNode;
    tail = newNode;
    length++;
    
    if (length == 1)
        head = tail;

  }

  /** 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 > length || index < 0) return;
    
    if (index == length) {
        addAtTail(val);
        return;
    }
    
    if (index == 0) {
        addAtHead(val);
        return;
    }
      
    Node *newNode = new Node(val);
    Node *prev = head;

    for (int i = 0; index - 1 > i; i++)
        prev = prev->next;
  
    newNode->next = prev->next;
    prev->next = newNode;
    length++;

  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  void deleteAtIndex(int index)
  {
      
    if (length == 0 || index >= length)
      return;
      
    else if (index == 0) {
        head = head->next;
        length--;
        return;
    }
       
      Node *prev = head;

      for (int i = 0; index - 1 > i; i++)
        prev = prev->next;
        
      Node *deleted = prev->next;
      prev->next = deleted->next;
          
      if (tail == deleted) 
          tail = prev;
          
      delete deleted;
    length--;
  }
};