# Leetcode 707. Design Linked List 練習
> Difficulty : `Medium`
> `Java` `演算法Algorithm`

> 撰寫人[name=KVJK_2125] [time=Fri, Mar 29, 2024 22:07]

## 題目
### 說明 Description
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.
- `int get(int index)` Get the value of the `index th` 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 `index th` 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 `index th` node in the linked list, if the index is valid.

### 範例 Example
Example 1:
> 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

### 限制條件 Constraints
- `0 <= index, val <= 1000`
- Please do not use the built-in LinkedList library.
- At most 2000 calls will be made to `get`, `addAtHead`, `addAtTail`, `addAtIndex` and `deleteAtIndex`.

## 解題
### 思路 Intuition/Approach
以Example 1做解釋：
- Step1.<br>先建立一個`class Node`，其中建立`val`存放值，`next`指向下一個node

- Step2.<br>在`MyLinkedList`中，建立一個空指標`Node head = null`，以及一個變數紀錄資料長度`int bruh = 0`

- Step3.整理函式內容<br>
-- <b>MyLinkedList()</b>：初始化。<br>
-- <b>get(index)</b>：<br>先判斷index是否有效（是否超出長度，或是否小於0）`index >= bruh || index < 0`，否則回傳`-1`。<br>有效則建立一個新節點`Node headtmp = head`，在執行`index`次內，指向`next`，在最後回傳值。<br>
-- <b>addAtHead(val)</b>：<br>建立一個新節點`Node veHead = new Node(val)`，將`veHead.next`指向`head`，再把`head`指向`vehead`，這樣就把新節點放入最前面了。<br>在最後長度記得加1`bruh++`。<br>
-- <b>addAtTail(val)</b>：<br>先判斷head是否為空（`head == null ?`）。<br>若為空的話，直接將`val`加入list即可（`head = new Node(val)`）；<br>若不為空，則建立一個指向`head`的新節點`Node headtmp = head`。直到`next`為空(`null`)之前，將新建的node指向`next`。<br>最後一個`next`指向`val`使其成為最後一個元素。<br>在最後長度記得加1`bruh++`。<br>
-- <b>addAtIndex(index, val)</b>：有點亂，我用寫的。<br><br>
--<b>addAtDelete(index)</b>：<br>先判斷index是否有效（是否超出長度，或是否小於0）`index >= bruh || index < 0`，<br>有效的話，建立一個指向`head`的新節點`Node current = head`，在建立一個指向空`null`的新節點`Node previous = null`。<br>在執行index次內，指向`next`。<br>結束後，若`previous == null`，則將`head`指向`next`；若`previous!=null`，則略過`current`，讓`previous.next`指向`current.next`，即刪除`current`。<br>在最後長度記得減1`bruh--`。<br>

### 程式碼 Code（加註解）

class MyLinkedList {
    Node head = null;   //建立空指標
    int bruh = 0;   //這個用來記錄長度
    
    //初始化
    public MyLinkedList() {
    }
    
    //取得下標為index的node的值。無效則回傳-1。
    public int get(int index) {
        //判斷是否有效
        if(index < 0 || index >= bruh)
            return -1;
        //建立指向head的node
        Node headtmp = head;
        //在index次數內，指向next
        for(int i = 0;i<index;i++)
           headtmp = headtmp.next;
        //如果不是空值，就回傳值
        return headtmp != null ? headtmp.val : 0; 
    }
    
    //將一個值為val的node插入第一個元素之前(vefore the first element)，成為linked list第一個node
    public void addAtHead(int val) {
        Node vehead = new Node(val);    //建立新的node
        vehead.next = head; //新node的下一個指向head
        head = vehead;  //head指向新node，讓新node成為first element
        bruh++;
    }
    
    //將一個值為val的node追加到linkedlist，成為最後一個元素(as the last element)
    public void addAtTail(int val) {
        //判斷head是不是null
        if(head == null){
            head = new Node(val);   //是空指標的話，就追加val
        }else{
           Node headtmp = head; //建立新node指向head
           while(headtmp.next != null) //直到next為空指標(null)之前
             headtmp = headtmp.next;    //將新建的node指向next
            headtmp.next = new Node(val);   //並成為val
        }
        bruh++; //長度記得++
    }
    
    //將一個值為val的node插入到下標為index的node前
    //如果index等於linked list的長度，該node會被追加到linked list的末端。
    //如果index大於linked list的長度，該node不會被寫入(will not be inserted)。
    public void addAtIndex(int index, int val) {
        if(index == bruh){
            addAtTail(val); //追加到末端
        }else if(index > bruh){
            return; //不寫入
        }else{
            Node veNode = new Node(val);
            if(head == null ){
                //如果head為空
                head = veNode;  //head指向新node
            }else if(index == 0){
                //如果index為0
                veNode.next = head; //新node的next指向head
                head = veNode;   //head指向新node
            }else{
                //建立分別指向head和null的node
                Node current = head;
                Node previous = null;
                //在index次數內
                for(int i = 0;i<index;i++){
                    previous = current; 
                    current = current.next; //指向next
                }
                veNode.next = current;  //新node的next指向最後
                previous.next = veNode; //指向新節點
            }
            bruh++; //長度記得++
        }
    }
    
    //如果下標有效(if the index is valid)，刪除表中下標為index的node
    public void deleteAtIndex(int index) {
        //判斷是否有效
        if(index < 0 || index >= bruh )
            return;
        //建立分別指向head和null的node
        Node current = head;
        Node previous = null;
        //在index次數內
        for(int i = 0;i<index;i++){
            previous = current;
            current = current.next; //指向next
        }
        if(previous == null){
            //將head指向next
            head = head.next;
        }else {
            //略過current，刪除
            previous.next = current.next;
        }
        bruh--; //長度記得--
    }
}

class Node{
    //題目說要叫做val跟next
    int val;
    Node next = null;
    public Node(int val){
        this.val = val;
    }
    public Node(int val, Node next){
        this.val = val;
        this.next = next;
    }
}