day05删除一個無頭單連結清單的非尾節點 +從尾到頭列印單連結清單+複雜連結清單的複制

• 1.删除一個無頭單連結清單的非尾節點，時間複雜度為O（1）

struct ListNode
{
    int val;
    ListNode *next;

    ListNode(int x):val(x),next(NULL) { }
};
//節點的後一個節點指派給要删除的節點，再删除這個後面的節點。
int DelNotTail(ListNode *delnode)
{
    if(delnode == NULL)
        return -;

    ListNode *pnext = delnode->next;
    delnode->val = pnext->val;
    delnode->next = pnext->next;
    delete pnext;

    return ;

           

• 從尾到頭列印單連結清單

struct ListNode
{
    int val;
    ListNode *next;

    ListNode(int x):val(x),next(NULL) { }
};

void Print(ListNode *phead)
{
    if(phead == NULL)
        return ;
    Print(phead->next);
    cout << phead->val <<endl;
}
           

• 複雜連結清單的複制

一個連結清單的每個節點，有一個指向next指針指向下一個節點，還有一個random指針指向這個連結清單中的一個随機節點或者NULL，現在要求實作複制這個連結清單，傳回複制後的新連結清單。

struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
        label(x), next(NULL), random(NULL) {
        }
};


RandomListNode* Clone(RandomListNode* pHead)
{
    if(pHead == NULL)
        return NULL;
    //第一步：每一個節點的後面插入一個新的節點
    RandomListNode *pcur = pHead;

    while(pcur)
    {
        RandomListNode *pm = new RandomListNode(pcur->label);
        pm->next = pcur->next;
        pcur->next = pm;

        pcur = pm->next;
    }

    //第二步：為每一個新節點的随機指針指派
    pcur = pHead;
    while(pcur)
    {
        RandomListNode *pnext = pcur->next;  //指向新的節點

        if(pcur->random == NULL)
            pnext->random = NULL;
        else
            pnext->random = pcur->random->next;

        pcur = pnext->next;
    }

    //第三步：将新的連結清單拆下來
    RandomListNode *ph = pHead->next;
    RandomListNode *pold = pHead;
    RandomListNode *pnew = ph;

    while(pnew)
    {
        pold->next = pnew->next;
        pold = pnew->next; //當pnew指向最後一個節點時，此時pold指向空了，
        pnew->next = (pold == NULL? NULL:pold->next);
        pnew =  (pold == NULL? NULL:pold->next);
    }

    return ph;
}