リンクリストのノード交換

反復解法

ListNode* swapPairs(ListNode* head) {
    if(!head || !head->next) return head;
    
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    ListNode* curr = head;
    
    while(curr && curr->next) {
        ListNode* nextNode = curr->next;
        
        // ノード交換
        prev->next = nextNode;
        curr->next = nextNode->next;
        nextNode->next = curr;
        
        // ポインタ更新
        prev = curr;
        curr = curr->next;
    }
    
    return dummy.next;
}

再帰解法

ListNode* swapPairsRecursive(ListNode* head) {
    if(!head || !head->next) return head;
    
    ListNode* newHead = head->next;
    head->next = swapPairsRecursive(newHead->next);
    newHead->next = head;
    
    return newHead;
}

末尾からN番目のノード削除

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;
    
    // ファストポインタをn+1ステップ進める
    for(int i = 0; i <= n; ++i) {
        fast = fast->next;
    }
    
    // スローとファストを同時に移動
    while(fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    // ノード削除
    ListNode* toDelete = slow->next;
    slow->next = toDelete->next;
    delete toDelete;
    
    return dummy.next;
}

リンクリストの交点検出

ハッシュセット解法

ListNode* getIntersectionNodeHash(ListNode* headA, ListNode* headB) {
    unordered_set<ListNode*> visited;
    
    while(headA) {
        visited.insert(headA);
        headA = headA->next;
    }
    
    while(headB) {
        if(visited.count(headB)) {
            return headB;
        }
        headB = headB->next;
    }
    
    return nullptr;
}

双ポインタ解法

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* ptrA = headA;
    ListNode* ptrB = headB;
    
    while(ptrA != ptrB) {
        ptrA = ptrA ? ptrA->next : headB;
        ptrB = ptrB ? ptrB->next : headA;
    }
    
    return ptrA;
}

循環リンクリストの検出

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if(slow == fast) {
            ListNode* entry = head;
            while(entry != slow) {
                entry = entry->next;
                slow = slow->next;
            }
            return entry;
        }
    }
    
    return nullptr;
}