鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。而雙向鏈表顧名思義通過指針域向前查找或者向后查找，且頭結點與尾節點直接相連構成環。

#ifndef DLIST_H
#define DLIST_H

// 數據類型，可根據需要自行定義
#define Item int 

// 鏈表節點信息 
typedef struct DLNode
{Item item;
    struct DLNode *prev;
    struct DLNode *next;
} DLNode;

typedef struct DList
{int size;
    DLNode *head;
} DList;

// Interfaces 
void InitDList(DList *dlist);
void InsertDlist(DList *dlist);
DLNode *searchDlist(Dlist *dlist);
void DeleteDlist(DList *dlist, const Item data);
void ShowDlist(const DList *dlist);
void freeDList(DList *dlist); 

#endif //DLIST_H

#include#include#include#include

// 初始化雙向鏈表，帶頭結點
void InitDList(DList *dlist)
{dlist->head = (DLNode *)malloc(sizeof(DLNode));
    if (dlist->head == NULL)
        return;

    dlist->size = 0;
    dlist->head->item = -1;
    dlist->head->prev = dlist->head;
    dlist->head->next = dlist->head;
}

// 鏈表項數
int DListcounts(DList *dlist)
{assert(dlist);
    return dlist->size;
}

// 插入數據 1）將數據封裝成節點    2）插入鏈表尾
void InsertDList(DList *dlist, const Item data)
{assert(dlist != NULL);
    DLNode *newnode = (DLNode *)malloc(sizeof(DLNode));
    if(newnode == NULL)
    {printf("out of memory !!\n");
        exit(1);
    }

    newnode->item = data;

    newnode->prev = dlist->head->prev;
    newnode->next = dlist->head;
    dlist->head->prev->next = newnode;
    dlist->head->prev = newnode;
    dlist->size++;
}

// 在循環鏈表中查找指定數據的節點
DLNode *searchDList(DList *dlist, const Item data)
{int i;
    assert(dlist != NULL);
    if(dlist->size == 0)
    {printf("the dlist is empty, do not find element:%d\n", data);
        return NULL;
    }

    DLNode *cur = dlist->head->next;
    for (i = 0; i< dlist->size; i++)
    {if(cur->item == data)
        {printf("find it ^_^!!!\n");
            return cur;
        }
        cur = cur->next;
    }

    if( i == dlist->size)
    {printf("unlucky, the element:%d is not exist in dlsit\n");
        return NULL;
    }
}

// 在雙向循環鏈表中獲取指定數據的節點，并返回
void deleteDList(DList *dlist, const Item data)
{DLNode *node = searchDList(dlist, data);
    if(node == NULL)
    {printf("the delete element is not exist in dlist!!\n");
        return;
    }

    node->prev->next = node->next; 
    node->next->prev = node->prev;
    dlist->size--;
    free(node);
    printf("delete it successfully!!\n");
    return ;
}


// 釋放構建鏈表所申請的堆內存
void freeDList(DList *dlist)
{DLNode *cur =NULL, *next = NULL;
    for (cur = dlist->head->next; cur != dlist->head; cur = next)
    {next = cur->next;       // 獲取下一個節點
        free(cur);          // 釋放節點
    }

    free(dlist->head);
    dlist->head = NULL;
}

// 主函數，對上述各接口調用
int main()
{DList list;
    DLNode *node;
    InitDList(&list);
    InsertDList(&list, 1);
    InsertDList(&list, 2);
    showDList(&list);
    node = searchDList(&list, 3);

    int counts1 = DListcounts(&list);
    printf("the counts of dlist is %d\n", counts1);

    deleteDList(&list, 1);

    int counts2 = DListcounts(&list);
    printf("the counts of dlist is %d\n", counts2);
    showDList(&list);
    freeDList(&list);
    return 0;
}

[postgres@test dlist_test]$ ./Dlist
1       2
unlucky, the element:3 is not exist in dlsit
the counts of dlist is 2
find it ^_^!!!
delete it successfully!!
the counts of dlist is 1
2

class Solution {public:
    Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1. 復制各節點，并構建拼接鏈表
        while(cur != nullptr) {Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 構建各新節點的 random 指向
        cur = head;
        while(cur != nullptr) {if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分兩鏈表
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 單獨處理原鏈表尾節點
        return res;      // 返回新鏈表頭節點
    }
};

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧