HackerRank‐Linked Lists - a920604a/leetcode GitHub Wiki

---

title: Linked Lists categories: - interview-preparation-kit - HackerRank comments: false

Insert a node at a specific position in a linked list

SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* llist, int data, int position) {
    SinglyLinkedListNode* ret = new SinglyLinkedListNode(-1), *p = ret;
    ret->next = llist;
    SinglyLinkedListNode * node = new SinglyLinkedListNode(data);
    while(position-->0) p=p->next;
    if(!p->next) {
        p->next = node;
        p->next->next = nullptr;
    }
    else{
        SinglyLinkedListNode * post = p->next;
        p->next = node;
        node->next = post;
    }
    return ret->next;
}

Inserting a Node Into a Sorted Doubly Linked List

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
    DoublyLinkedListNode * node = new DoublyLinkedListNode(data);
    DoublyLinkedListNode* ret = new DoublyLinkedListNode(-1), *p=ret;
    p->next = llist;
    DoublyLinkedListNode * pre ;
    while(p && p->data < data) {
        pre = p;
        p=p->next;
    }
    if(p==nullptr){
        pre->next= node;
        node->prev = pre;
    }
    else{
        p->prev = node;
        node->next = p;
        node->prev = pre;
        pre->next = node;
    }
    return ret->next;

}

Reverse a doubly linked list

DoublyLinkedListNode* reverse(DoublyLinkedListNode* llist) {
    if(!llist || !llist->next) return llist;
    DoublyLinkedListNode * pre = nullptr, *cur = llist;
    while(cur->next){
        DoublyLinkedListNode * post = cur->next;
        cur->next = pre;
        if(pre) pre->prev=cur;
        pre=cur;
        cur=post;
    }
    cur->next = pre;
    if(pre) pre->prev=cur;
    return cur;
}

Find Merge Point of Two Lists

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    
    SinglyLinkedListNode *p = head1, *q=head2;
    while(p != q){
        if(p->next == nullptr) p=head1;
        else p=p->next;
        if(q->next == nullptr) q=head2;
        else q=q->next;
    }
    return p->data;
}

Linked Lists: Detect a Cycle

bool has_cycle(Node* head) {
    // Complete this function
    // Do not write the main method
    Node *slow =head, *fast = head;
    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast) return true;
    }
    return false;
}