Leetcode 707. Design Linked List 練習

Difficulty : Medium
Java 演算法Algorithm

撰寫人KVJK_2125Fri, 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.
  先建立一個class Node，其中建立val存放值，next指向下一個node

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

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

  
  
  –addAtDelete(index)：
  先判斷index是否有效（是否超出長度，或是否小於0）index >= bruh || index < 0，
  有效的話，建立一個指向head的新節點Node current = head，在建立一個指向空null的新節點Node previous = null。
  在執行index次內，指向next。
  結束後，若previous == null，則將head指向next；若previous!=null，則略過current，讓previous.next指向current.next，即刪除current。
  在最後長度記得減1bruh--。
  

程式碼 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;
    }
}