老青菜

剑指offer-在O(1)时间删除链表结点

2017-01-22

题目

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

分析

在单向链表中删除一个结点,一般的做法是从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点。时间复杂度O(n)
这里我们介绍一种巧妙的方法:

  1. 一个链表,要删除节点a,a后面的节点是b。
  2. 把b内容复制覆盖a。
  3. a的next指针指向b的next。

实现

void deleteNode(ZHNode *hNode, ZHNode *delNode) {
    if (hNode == NULL || delNode == NULL) {
        //节点为空
        return;
    }
    if (delNode == hNode) {
        //删除头节点
        hNode->next = NULL;
    } else if (delNode->next == NULL) {
        //删除尾节点
        ZHNode *tmpNode = hNode;
        while (tmpNode->next != NULL) {
            tmpNode = tmpNode->next;
        }
        //找到尾节点的上一个节点
        tmpNode->next = NULL;
    } else {
        //删除其他节点
        delNode->data = delNode->next->data;
        delNode->next = delNode->next->next;
    }
}
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章