爱悠闲 > 奇思妙想:删除单链表的一个节点

奇思妙想:删除单链表的一个节点

分类: 算法  |  标签: 单链表,删除  |  作者: souldak 相关  |  发布日期 : 2014-08-08  |  热度 : 1284°

Cracking the Coding Interview 中的一个题目,非常巧妙:

Implement an algorithm to delete a node in the middle of a single linked list, given

only access to that node
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e

Result: nothing is returned, but the new linked list looks like a->b->d->e


题目只给了要删除的节点,我们没法找到该几点的上一个节点。常规的做法是将前一个节点的next指向下一个节点,然后删除当前节点。显然现在这个方法行不通了,因为我们没有办法获得前一个节点。

那怎么做呢?

Cracking the Coding Interview给出了一个很巧妙的解法,将后一个节点的信息copy到当前的节点,然后删除下一个节点!Amazing!

不过这个方法有个弊端: 无法删除最后一个节点。 但是这不影响它对我们思考问题的启发,突破常规,换一个角度去想,往往能得到意想不到的答案。