leet code 문제 풀이

1294 - Design Linked List

C++ time(beats 81.95%) space(beats 0%)

struct Node
{
    Node* prev;
    Node* next;
    int val;
};

class MyLinkedList {
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        _head = new Node();
        _tail = new Node();

        _head->next = _tail;
        _tail->prev = _head;
        _len=0;
    }

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

        Node* ptr = _head->next;
        for(int i=0; i<index; ++i)
        {
            ptr = ptr->next;
        }
        return ptr->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* ptr = new Node();
        ptr->val = val;
        ptr->prev = _head;
        ptr->next = _head->next;
        _head->next->prev = ptr;
        _head->next = ptr;

        _len++;
    }

    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        Node* ptr = new Node();
        ptr->val = val;
        ptr->prev = _tail->prev;
        ptr->next = _tail;
        _tail->prev->next = ptr;
        _tail->prev = ptr;

        _len++;
    }

    /** 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) {
        Node* ptr = _head;
        Node* newItem = new Node();

        if(index>_len) return;

        for(int i=0; i<index; ++i) ptr=ptr->next;
        newItem->val = val;
        newItem->prev = ptr;
        newItem->next = ptr->next;
        ptr->next->prev = newItem;
        ptr->next = newItem;

        _len++;
        return;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if(index >= _len) return;

        Node* ptr = _head->next;
        for(int i=0; i<index; ++i) ptr=ptr->next;
        ptr->prev->next = ptr->next;
        ptr->next->prev = ptr->prev;

        _len--;
    }

private:
    Node* _head;
    Node* _tail;
    int _len;
};

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

1227 Merge Two Sorted Lists

C++ time(beats 24.92%), memory(beats 35.16%)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode();
        ListNode* prev = head;

        ListNode* ptr1 = l1;
        ListNode* ptr2 = l2;

        while(ptr1!=nullptr || ptr2!=nullptr)
        {
            if(ptr1!=nullptr&&ptr2!=nullptr)
            {
                if(ptr1->val <= ptr2->val)
                {
                    prev->next = ptr1;
                    ptr1 = ptr1->next;
                    prev = prev->next;
                }else
                {
                    prev->next = ptr2;
                    ptr2 = ptr2->next;
                    prev = prev->next;
                }
            }else if(ptr1==nullptr&&ptr2!=nullptr)
            {
                prev->next = ptr2;
                ptr2 = ptr2->next;
                prev = prev->next;
            }else if(ptr1!=nullptr&&ptr2==nullptr)
            {
                prev->next = ptr1;
                ptr1 = ptr1->next;
                prev = prev->next;
            }

        }
        return head->next;

    }
};

1228 - Add Two Numbers

C++ time(beats 80.35%), space(beats 28.41%)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode();
        ListNode* ptr = head;
        int carry = 0;
        int val = 0;
        while(l1||l2)
        {
            if(l1 && l2)
            {
                val = l1->val + l2->val;
                l1 = l1->next;
                l2 = l2->next;
            }else if(l1 && !l2)
            {
                val = l1->val;
                l1 = l1->next;
            }else if(!l1 && l2)
            {
                val = l2->val;
                l2 = l2->next;
            }
            ptr->next = new ListNode((val+carry)%10);
            carry = (val+carry)/10;
            ptr = ptr->next;
        }
        if(carry)
        {
            ptr->next = new ListNode(carry);
        }
        return head->next;
    }
};

1226 - Insert into a Sorted Circular Linked List

C++ time(beats 97.78%), memory(beats 64.95%)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if(head)
        {
            // find minimum value
            int minVal = head->val;
            Node* minPtr = head;
            Node* ptr = head->next;

            while(ptr!=head)
            {
                if(ptr->val < minVal)
                {
                    minPtr = ptr;
                    minVal = ptr->val;
                }
                ptr = ptr->next;
            }

            ptr = minPtr;
            while(ptr->next!=minPtr)
            {
                if(insertVal >= ptr->val && insertVal <= ptr->next->val)
                {
                    Node* newNode = new Node(insertVal, ptr->next);
                    ptr->next = newNode;
                    return head;
                }
                ptr = ptr->next;
            }
            Node* newNode = new Node(insertVal, ptr->next);
            ptr->next = newNode;
            return head;

        }else
        {// head is null
            Node* newNode = new Node(insertVal);
            newNode->next = newNode;
            return newNode;
        }
    }
};

1295 - Rotate List

C++ time(beats 98.83%), space(beats 0%)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        ListNode* ptr = head;
        ListNode* tail = head;
        ListNode* tmp = nullptr;
        int nodeLen = 0;
        while(ptr)
        {
            nodeLen++;
            if(ptr->next == nullptr) tail = ptr;
            ptr = ptr->next;
        }
        printf("%d\n", tail->val);

        k = k%nodeLen;
        if(k==0) return head;
        ptr = head;
        for(int i=0; i<(nodeLen-k-1); ++i)
        {
            ptr = ptr->next;
        }
        tail->next = head;
        head = ptr->next;
        ptr->next = nullptr;
        return head;
    }
};

3238 - Max Consecutive Ones

C++ time(beats 45.39%) space(57.29%)

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int rslt = 0;
        int maxVal = 0;
        for(int i=0; i<nums.size(); ++i)
        {
            if(nums[i])
            {
                rslt++;
                if(rslt > maxVal)
                    maxVal = rslt;
            }else
            {
                rslt = 0;
            }
        }
        return maxVal;
    }
};