• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

4小时前 2次浏览

# linus 提到过的单链表删除节点算法

## 1 问题描述

linus在TED演讲_哔哩哔哩_bilibili

``````remove_list_entry(entry)
{
prev = NULL;
while (walk && walk!=entry)
{
prev = walk;
walk = walk->next;
}

// Remove the entry by
// updating the head or previous entry
if (!prev)
{
}
else
{
prev->next = entry->next;
}

// 释放节点空间
free(entry);
}
``````

``````remove_list_entry(entry)
{
// The "inderect" pointer points to the
// *address* of of the thing we will update

// Walk the list, looking for the thing that points to
// entry we want to remove entry
while ((*indirect)&&(*indirect)!=entry)
{
indirect = &(indirect->next);
}

// just remove the entry
*indirect = entry->next;
free(entry);
}
``````

## 2 思路

### 解法1，是常用的解法

#### 特殊情况

• 整个链表只有2个节点的情况

• 整个链表只有1个节点的情况

### 解法2

#### 二重指针

`indirect=&head`

``````typedef struct ListNode
{
ListNode* next;
int data;
} ListNode;
``````

1. 下一个节点的地址
2. 本身数据

#### 具体操作

``````while (*indirect && *indirect != entry)
{
indirect = &(*indirect->next);
}
``````

``````    // just remove the entry
*indirect = entry->next;
free(entry);
``````