LeetCode - 707. Design Linked List(LinkedList, Design)*

문제

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

https://leetcode.com/problems/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.

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

풀이

자바입니다.

• 예외처리에 주의해야합니다.

class MyLinkedList {
    
    private ListNode head;
    
    public static class ListNode{
        private int data;
        private ListNode next;
        
        public ListNode(int data){
            this.data = data;
            this.next = null;
        }
    }

    public MyLinkedList() {
        this.head=null;
    }
    
    public int get(int index) {
         if(index < 0 || index >= size()) {
            return -1;
        }
        
        if(index==0){
            return head.data;
        }
        if(index>=size()){
            return -1;
        }
           
        ListNode current = head;
        int pos=0;
        while(pos!=index){
            current = current.next;
            pos++;
        }
        return current.data;    
        
        
        
    }
    
    public void addAtHead(int val) {
        if(head==null){
            head=new ListNode(val);
        }else{
            ListNode newHead = new ListNode(val);
            newHead.next=head;
            head=null;
            head=newHead;
        }
    }
    
    public void addAtTail(int val) {
        if(head==null){
            addAtHead(val);
            return;
        }
        ListNode current = head;
        while(current.next!=null){
            current=current.next;
        }
        current.next=new ListNode(val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size()){
            return;
        }
        if(index==0){
            addAtHead(val);
            return;
        }
        if(index==size()){
            addAtTail(val);
            return;
        }
        ListNode current = head;
        int pos = 0;
        while(pos!=index-1){
            pos++;
            current=current.next;
        }
        ListNode addNode = new ListNode(val);
        addNode.next=current.next;
        current.next=addNode;
        
    }
    
    public void deleteAtIndex(int index) {
         if(index < 0 || index >= size()) {
            return;
        }
        
        if(index==0){
            head=head.next;
            return;
        }
        
        ListNode current = head;
        ListNode pre = null;
        int pos = 0;
        while(pos!=index){
            pre = current;
            current = current.next;
            pos++;
        }
        
        pre.next=current.next;
              
    }
    
    //LinkedList의 크기 반환
    public int size(){
        if(head==null){
            return 0;
        }
        ListNode current = head;
        int pos=0;
        while(current!=null){
            current=current.next;
            pos++;
        }
        return pos;
    }
}

/**
 * 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);
 */

size() 메서드를 만들지 않고 int size 변수를 선언해서 코딩했다면 런타임시간을 줄일 수 있을 것이다.