GeekPractice_LinkedList - meruneru/tech_memo GitHub Wiki

GeekPractice

解いた問題の備忘録

Detect Loop in linked List

問題

ListがLoopしてたらTrue, LoopしてなければFalseを返す関数を作る。

問題のNが最大でも$10^4$だったので、nextを何回たどれるかで判定した。

class Solution
{
    public:
    //Function to check if the linked list has a loop.
    bool detectLoop(Node* head)
    {
        if(head->next==NULL){
            return false; //no Loop
        }

        Node* node=head;
        int cnt = 0;
        while(1){
            if(node==NULL){
                return false;
            }
            if(cnt>10000){
                break;
            }
            node=node->next;
            cnt++;
        }
        return true;
    }
};

正攻法

辿ったノードのアドレスを保存していき、 同じアドレスを保存する場合は、Loopと判断する。

std::unordered_setとstd::setの違い

std::setはinsertするたびに並び替えを行うが、std::unordered_setは並び替えない。 順番を意識する必要がない場合は、unordered_setの方が早くていい。

#include <unordered_set>
class Solution
{
    public:
    //Function to check if the linked list has a loop.
    bool detectLoop(Node* head)
    {
        std::unordered_set<Node*> h;
        Node* node=head;
        while(node){
            if(h.find(node) != h.end()){
                return true; // Already saved because of loop
            }
            h.insert(node);
            
            node=node->next;
        }
        return false;
    }
};

Quick Sort on Linked List

問題

QuickSortを実装しなさいという問題だが、LinkedListは先頭からノードを辿るしかできず、ランダムアクセスが$O(1)$でできない。

そのため、LinkedListのdataだけ取り出して、std::sortで並び替えて再度セットした。

std::sortは優秀で、常にO(NlogN)のようだ。 QuickSortの改良版であるイントロソートが使われているらしい。 std::sortのリファレンス 備考

#include<vector>
#include<algorithm>
//you have to complete this function
void quickSort(struct node **headRef) {
    std::vector<int> v;
    
    struct node* current=*headRef;
    while(current){
        v.push_back(current->data);
        current=current->next;
    }
    std::sort(v.begin(), v.end());
    current=*headRef;
    for(size_t i=0; i<v.size(); i++){
        current->data = v[i];
        current=current->next;
    }
}

正攻法

解答を見ると下記リンクのみが記載されていた。 やはり、きちんとQuicksortを実装すべきだったようだ。 QuickSort on Singly Linked List

⚠️ **GitHub.com Fallback** ⚠️