Linked List

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* pre = &dummy;
        ListNode* cur = head;

        while (cur) {
            while (cur && cur->next && cur->val == cur->next->val) cur = cur->next;
            pre->next = cur;
            pre = cur;
            if (cur) cur = cur->next;
        }
        if (pre) pre->next = nullptr;

        return dummy.next;
    }
};

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head || m == n) return head;

        ListNode* pre = nullptr;
        ListNode* cur = head;
        int start = m;
        while (--start && cur) {
            pre = cur;
            cur = cur->next;
        }
        if (start != 0 || !cur) return head;

        ListNode* head1 = cur;
        ListNode* pre1 = cur;
        ListNode* cur1 = cur->next;
        int cnt = n - m;

        while (cur1 && cnt--) {
            ListNode* tmp = cur1->next;
            cur1->next = pre1;
            pre1 = cur1;
            head1 = cur1;
            cur1 = tmp;
        }

        if (pre) pre->next = head1;
        cur->next = cur1;
        if (m == 1) return head1;
        return head;
    }

    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* cur = head;
        ListNode* next = head->next;
        cur->next = nullptr;
        ListNode* newHead = reverseList(next);
        next->next = cur;
        return newHead;
    }
};

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        ListNode* next = head->next;

        while (cur) {
            while (cur && cur->next && cur->val == cur->next->val) {
                int val = cur->val;
                while (cur && cur->val == val) cur = cur->next;
            }

            //if (pre)
            pre->next = cur;
            pre = cur;
            if (cur) cur = cur->next;
        }

        head = dummy->next;
        delete dummy;
        return head;

    }
};

138. Copy List with Random Pointer

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return nullptr;

        RandomListNode* cur = head;
        RandomListNode* pre = nullptr;
        while (cur) {
            RandomListNode* copy = new RandomListNode(cur->label);
            copy->next = cur->next;
            cur->next= copy;
            cur = copy->next;
        }
        pre = head;
        cur = head->next;
        while (cur) {
            if (pre->random)
                cur->random = pre->random->next;
            else
                cur->random = nullptr;
            pre = cur->next;
            if (!pre) break;
            cur = pre->next;
        }

        RandomListNode* newHead = head->next;
        pre = head;
        cur = head->next;
        while (cur) {
            pre->next = cur->next;
            pre = cur->next;
            if (!pre) break;
            cur->next = pre->next;
            cur = pre->next;
        }

        return newHead;

    }
};

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;
        ListNode* slow = head;
        ListNode* fast = head;
        bool hasCycle = false;
        while (fast) {
             if (!fast->next) return nullptr;
             fast = fast->next->next;
             slow = slow->next;
             if (fast == slow) {
                 hasCycle = true;
                 break;
             }
        }
        if (!hasCycle) return nullptr;

        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

class LRUCache{
public:
    LRUCache(int capacity) : capacity(capacity) {

    }

    int get(int key) {
        int ret = -1;
        if (cache.find(key) != cache.end()) {
            ret = cache[key]->second;
            visit_queue.splice(visit_queue.begin(), visit_queue, cache[key]);
        }
        return ret;
    }

    void set(int key, int value) {
        if (cache.find(key) != cache.end()) {
            cache[key]->second = value;
            visit_queue.splice(visit_queue.begin(), visit_queue, cache[key]);
        } else {
            if (cache.size() == capacity) {
                cache.erase(visit_queue.back().first);
                visit_queue.pop_back();
            }
            visit_queue.push_front({key, value});
            cache[key] = visit_queue.begin();
        }
    }

private:
    unordered_map<int, list<pair<int, int>>::iterator> cache;
    list<pair<int, int>> visit_queue;
    int capacity;
};

147. Insertion Sort List

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode dummy(0);
        // dummy.next = head;

        ListNode* cur = head;
        ListNode* next = nullptr;

        while (cur) {
            next = cur->next;
            cur->next = nullptr;
            // insert cur to the list;
            ListNode* pre = &dummy;
            ListNode* tmp = dummy.next;
            while (tmp && tmp->val < cur->val) {
                    pre = tmp;
                    tmp = tmp->next;
            }
            pre->next = cur;
            cur->next = tmp;

            // move to next value;
            cur = next;
        }
        head = dummy.next;
        return head;
    }
};

206. Reverse Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        // ListNode* pre = head;
        // ListNode* cur = head->next;
        // pre->next = nullptr;
        // ListNode* newHead = nullptr;
        // while (cur) {
        //     ListNode* next = cur->next;
        //     cur->next = pre;
        //     pre = cur;
        //     newHead = cur;
        //     cur = next;
        // }
        // return newHead;

        ListNode* cur = head;
        ListNode* next = head->next;
        cur->next = nullptr;
        ListNode* newHead = reverseList(next);
        next->next = cur;
        return newHead;

    }
};

results matching ""

    No results matching ""