【剑指Offer】T18 删除链表节点

题目一:O(1)时间内删除链表结点
给定单链表头指针和一个结点的指针,定义一个函数在 O(1)时间内删除该结点。

常规思想:向后p->next,直到找到该结点,然后调整指针删除,复杂度为O(n)。这样做的原因是需要直到该节点的前一个结点。

void DeleteNode(LinkList** L, LinkList *pToBeDelete){
      LinkList *pre = L;
    while(pre->next != nullptr){
        LinkList *q = pre->next;
        // 结点在末尾的情况
        if(q ->next == nullptr){
            pre->next = nullptr;
            delete q;
            q = nullptr;
            return;
        }
        
        if(q == pToBeDelete){
            pre->next = q->next;
            delete q;
            q = nullptr;
            return;
        }
        
        pre = pre->next;
    }
}

1566283592933.png

高级思想,复杂度为 1 :后继结点赋值到本身,然后删除后继结点

void DeleteNode(LinkList** L, LinkList *pToBeDelete){
      
    LinkList *q = pToBeDelete->next; // 记录以删除结点
    
    pToBeDelete->data = pToBeDelete->next->data;
    pToBeDelete->next = pToBeDelete->next->next;
    // 也可用q表示
    // pToBeDelete->data = q->data;
    // pToBeDelete->next = q->next;
    delete q;
    q = nullptr;
}

1566284094823.png

加上几种特殊情况:

  • 删除结点位于尾部:遍历求解
  • 链表中只有一个结点:删除结点,并设置头结点为nullptr

完整代码:

void DeleteNode(LinkList** L, LinkList *pToBeDelete){
      // 结点在末尾的情况
    if(pToBeDelete->next == nullptr){
        LinkList *pre = *L;
        while(pre->next != pToBeDelete){
            pre = pre->next;
        }
        // 此时pre->next == pToBeDelete
        pre->next = nullptr;
        // 清理
        delete pToBeDelete;
        pToBeDelete = nullptr;
    }
    // 只有一个结点
    else if(*L == pToBeDelete){
        delete pToBeDelete;
        pToBeDelete = nullptr;
        *L = nullptr;
    } else { // 普通情况
        LinkList *q = pToBeDelete->next; // 记录以删除结点
    
        pToBeDelete->data = pToBeDelete->next->data;
        pToBeDelete->next = pToBeDelete->next->next;
        // 也可用q表示
        // pToBeDelete->data = q->data;
        // pToBeDelete->next = q->next;
        delete q;
        q = nullptr;
    }
}

T18-2 删除链表重复结点

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表 1 ->2->3->3->4->4->5 处理后为 1->2->5

我的思路:

ListNode* deleteDuplicates(ListNode* head) {
    if(head == NULL)
        return head;

    ListNode* p = head;
    ListNode* pre = NULL; // 记录p前驱
    int flag = 0; // 记录是否发生删除操作

    while(p->next != NULL){
        pre = p;
        ListNode* pn = p->next; // p后继
        while(pn->next != NULL){ // 向后遍历
            if(pn->val == p->val){ // 后继和p相同
                pn = pn->next; //后继前进
                flag = 1;
                // 删除操作
            }else // 直到不相等,跳出遍历
                break;
        }

        if(flag == 1){ // 发生删除操作
            flag = 0;

            p->val = pn->val;

            if(pn->next == NULL){ // pn为末尾结点
                if(pn->val == p->val){ // [1, 1],最后两个结点相同的情况
                    pre->next = NULL;
                    break;
                }
                p->next = NULL;
            }
            else
                p->next = pn->next;

        }else
            p = p->next; // 无操作,前进
    }
    return head;
}

通不过测试用例[1,1][0,1,1,2,2](末尾有相同数字)

ListNode* deleteDuplication(ListNode* head){
    ListNode* p = new ListNode(0);
    p->next = head;
    head = p;
    ListNode *left,*right;
    while(p->next){
        left = p->next;
        right = left;
        while(right->next && right->next->val==left->val) // 1
            right = right->next;
        if(left == right) // 2
            p = p->next;
        else // 3 
            p->next =right->next;
    }
    return head->next;
}

1566307499061.png

本文链接:https://ariser.cn/index.php/archives/159/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!