[Medium] 707. Design Linked List

문제

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 indexth 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 indexth 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 indexth node in the linked list, if the index is valid.

 

링크된 목록의 구현을 설계합니다. 단일 또는 이중으로 연결된 목록을 사용하도록 선택할 수 있습니다.
단일 링크 목록의 노드는 val과 next의 두 가지 속성을 가져야 합니다. val은 현재 노드의 값이고, 다음은 다음 노드에 대한 포인터/참조입니다.
이중 링크 목록을 사용하려면 링크 목록에서 이전 노드를 나타내려면 미리 하나의 속성이 더 필요합니다. 연결된 목록의 모든 노드가 0인 것으로 가정합니다.

MyLinkedList 클래스 구현:

MyLinkedList() MyLinkedList 개체를 초기화합니다.
intget(int index) 링크된 목록의 인덱스 노드 값을 가져옵니다. 인덱스가 유효하지 않으면 -1을 반환합니다.
void addAtHead(intval) 링크된 목록의 첫 번째 요소 앞에 값 값의 노드를 추가합니다. 삽입 후 새 노드가 연결 목록의 첫 번째 노드가 됩니다.
void addAtTail(intval) 값 노드를 링크된 목록의 마지막 요소로 추가합니다.
추가 무효 AIndex(int index, intval) 링크된 목록의 인덱스 노드 앞에 값 노드를 추가합니다. 인덱스가 연결된 목록의 길이와 같으면 노드가 연결된 목록의 끝에 추가됩니다. 인덱스가 길이보다 크면 노드가 삽입되지 않습니다.
삭제 무효 At인덱스(int 인덱스) 인덱스가 유효한 경우 링크된 목록에서 인덱스 노드를 삭제합니다.

 

예시

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.

 

해결 코드

let singleLinkNode = function(value){
    this.value = value;
    this.next = null;
};

let MyLinkedList = function(head = null) {
    this.head = head;
    this.length = 0;
};

MyLinkedList.prototype.getNode = function(index){
    if(index < 0 || index > this.length - 1) return null;
    let current = this.head;
    let count = 0;
    while(current && count < index){
        current = current.next;
        count++;
    }
    return current;
}

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    let current = this.getNode(index);
    return current === null ? -1 : current.value;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let newHead = new singleLinkNode(val);
    newHead.next = this.head;
    this.head = newHead;
    this.length++;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let current = this.head;
    if(current === null){
        this.head = new singleLinkNode(val);
        current = new singleLinkNode(val);
        this.length++;
        return;
    } 
    while(current && current.next){
        current = current.next;
    }
    current.next = new singleLinkNode(val);
    this.length++;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index == 0){
        this.addAtHead(val);
    }else if(index == this.length){
        this.addAtTail(val);
    }else if(index < this.length && index > 0){
        let current = this.getNode(index);
        let prev = this.getNode(index - 1);
        let node = new singleLinkNode(val);
        prev.next = node;
        node.next = current;
        this.length++;
    }
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    let current = this.getNode(index);
    if(current === null) return;
    let prev = this.getNode(index - 1);
    let next = current.next;
    if(prev !== null){
        prev.next = next;
    }else{
        this.head = next;
    }
    this.length--;
};

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