cpp-algo-cases/chapter_array_and_linkedlist/linked_list.cpp

/**
 * File: linked_list.cpp
 * Created Time: 2022-11-25
 * Author: krahets (krahets@163.com)
 */

#include "../utils/common.hpp"

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľڵ<C4BD> n0 ֮<><D6AE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD> P */
void insert(ListNode *n0, ListNode *P)
{
    ListNode *n1 = n0->next; // n0 -> n1
    P->next = n1;            // P -> n1
    n0->next = P;            // n0 -> P
}

/* ɾ<><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľڵ<C4BD> n0 ֮<><D6AE><EFBFBD><EFBFBD><EFBFBD>׸<EFBFBD><D7B8>ڵ<EFBFBD> */
void remove(ListNode *n0)
{
    if (n0->next == nullptr)
        return; // n0 ֮<><D6AE>û<EFBFBD>нڵ<D0BD>
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // <20>ͷ<EFBFBD><CDB7>ڴ<EFBFBD>
    delete P;
}

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ index <20>Ľڵ<C4BD> */
ListNode *access(ListNode *head, int index)
{
    for (int i = 0; i < index; i++)
    {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>в<EFBFBD><D0B2><EFBFBD>ֵΪ target <20><><EFBFBD>׸<EFBFBD><D7B8>ڵ<EFBFBD> */
int find(ListNode *head, int target)
{
    int index = 0;
    while (head != nullptr)
    {
        if (head->val == target) // <20>ҵ<EFBFBD><D2B5>ڵ<EFBFBD>
            return index;        // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
        head = head->next;       // <20><><EFBFBD>½ڵ<C2BD>
        index++;                 // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    }
    return -1; // δ<>ҵ<EFBFBD><D2B5>ڵ<EFBFBD>, <20><><EFBFBD><EFBFBD> -1
}

/* Driver Code */
int main()
{
    /* <20><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
    // <20><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
    ListNode *n0 = new ListNode(1); // <20><><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>, ֵΪ1
    ListNode *n1 = new ListNode(3);
    ListNode *n2 = new ListNode(2);
    ListNode *n3 = new ListNode(5); // <20><><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>, ֵΪ5
    ListNode *n4 = new ListNode(4);
    // <20><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>֮<EFBFBD><D6AE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    n0->next = n1;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    cout << "<EFBFBD><EFBFBD>ʼ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ" << endl;
    printLinkedList(n0);

    /* <20><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD> */
    insert(n0, new ListNode(0));
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ" << endl;
    printLinkedList(n0);

    /* ɾ<><C9BE><EFBFBD>ڵ<EFBFBD> */
    remove(n0);
    cout << "ɾ<EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ" << endl;
    printLinkedList(n0);

    /* <20><><EFBFBD>ʽڵ<CABD> */
    ListNode *node = access(n0, 3);
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> 3 <20><><EFBFBD>Ľڵ<C4BD><DAB5><EFBFBD>ֵ = " << node->val << endl;

    /* <20><><EFBFBD>ҽڵ<D2BD> */
    int index = find(n0, 2);
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵΪ 2 <20>Ľڵ<C4BD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> = " << index << endl;

    // <20>ͷ<EFBFBD><CDB7>ڴ<EFBFBD>
    freeMemoryLinkedList(n0);

    return 0;
}