如何删除 linked list 的最后一个元素 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

如何删除 linked list 的最后一个元素 (转载)

如何删除 linked list 的最后一个元素 (转载)# JobHunting - 待字闺中

l*i2013-02-15 08:02

1 楼

【以下文字转载自 Java 讨论区】
发信人: lvshi (虑始), 信区: Java
标题: 如何删除 linked list 的最后一个元素
发信站: BBS 未名空间站 (Fri Feb 15 15:31:23 2013, 美东)
parameter 只有一个 Node，要被删除。
private static boolean removeNode(Node toRemoved)
{
if(toRemoved == null)
{
return false;
}
if(toRemoved.next == null) //This is not working.
{
toRemoved = null;
return true;
}
Node next = toRemoved.next;
toRemoved.data = next.data;
toRemoved.next = next.next;
return true;
}
我想这个node如果是最后一个元素的话，设其为 null
但是实际跑的时候，发现这个node并没有删除。请问为什么？有什么办法直接删除
linked list 的最后一个元素？
多谢。

S*I2013-02-15 08:02

2 楼

The previous node's next needs to be set to null.

【在 l***i 的大作中提到】

: 【以下文字转载自 Java 讨论区】
: 发信人: lvshi (虑始), 信区: Java
: 标题: 如何删除 linked list 的最后一个元素
: 发信站: BBS 未名空间站 (Fri Feb 15 15:31:23 2013, 美东)
: parameter 只有一个 Node，要被删除。
: private static boolean removeNode(Node toRemoved)
: {
: if(toRemoved == null)
: {
: return false;

c*t2013-02-15 08:02

3 楼

木有办法
除非能有方法找previous node

【在 l***i 的大作中提到】

l*i2013-02-15 08:02

4 楼

这个问题很贱，有一种做法是swap两个node的实际内容，然后删除后一个。当然如果要
删除的是tail就没办法这么搞了。
typedef int ItemType;
struct node {
ItemType val;
node *next;
};
node* delete(node *ptr)
{
if (ptr == NULL) return;
if (ptr->next == NULL) return; // do something like report error
node *next = ptr->next;
swap(ptr->val, next->val);
ptr->next = next->next;
next->next = NULL;
return next;
}

s*w2013-02-15 08:02

5 楼

你这个delete function 错了吧，难道不用先循环往下找最后一个 node?

【在 l***i 的大作中提到】

: 这个问题很贱，有一种做法是swap两个node的实际内容，然后删除后一个。当然如果要
: 删除的是tail就没办法这么搞了。
: typedef int ItemType;
: struct node {
: ItemType val;
: node *next;
: };
: node* delete(node *ptr)
: {
: if (ptr == NULL) return;

l*i2013-02-15 08:02

6 楼

请注意，这个问题要求parameter只有一个，就是当前的node的pointer，没有整个list
的信息。
lanti的做法应该和我的基本一致。
我的问题是，既然倒数第二个的next指向最后一个，那我把最后一个设为null，不就相
当与删除了这个node吗？是不是有什么java底层的东西我搞错了？

p*p2013-02-15 08:02

7 楼

你这在C++里也不行啊，除非你把函数参数定义成引用
removeNode(Node * &toRemoved)
这样的
java里可以把返回值定义成Node
if (toRemoved == null) return null;
if (toRemoved->next == null) return null;
toRemoved->next = removeNode(toRemoved->next);
return toRemoved;
你光把最后一个node改成null只是影响了局部变量而已，上一个node的next还是原来的
指向

list

【在 l***i 的大作中提到】

: 请注意，这个问题要求parameter只有一个，就是当前的node的pointer，没有整个list
: 的信息。
: lanti的做法应该和我的基本一致。
: 我的问题是，既然倒数第二个的next指向最后一个，那我把最后一个设为null，不就相
: 当与删除了这个node吗？是不是有什么java底层的东西我搞错了？

m*g2013-02-15 08:02

8 楼

上一楼说过了：虽然只有一个传入参数，你可以往下查两层啊。
还有一个办法就是swap这个和下一个node的内容。这个应该是更好的方法。

t*e2013-02-15 08:02

9 楼

Swapping with the next node is the best solution. C++ code in here https://
code.google.com/p/elements-of-programming-interviews/source/browse/trunk/
Deletion_list_template.cpp
P.S. This solution came from Elements of Programming Interviews: 300
Questions
and Solutions http://www.amazon.com/dp/1479274836/.

r*j2013-02-15 08:02

10 楼

你所说的把最后一个设成null，只是把某一个指向最后一个node的reference设为null
了，还会有其他reference知道这个最后一个node在哪，比如previous node的next。你
只是杀了一个知道真相的目击证人，还有其他人也知道真相。。。

list

【在 l***i 的大作中提到】

c*a2013-02-15 08:02

11 楼

这样算不算作弊......
public void delete(ListNode node){
if(node == null) return;
while(node.next!=null){
node.val=node.next.val;
node=node.next;
}
node=null;
}

l*i2013-02-15 08:02

12 楼

在C＋＋里可以用pointer的reference直接改变一个memory location的值，比如下面这个
#include
using namespace std;
void update(int*);
int main()
{
int x = 5;
int* pi = &x;
cout << "Before update, " << x << endl;

update(pi);
cout << "After update, " << x << endl;
return 0;
}
void update(int* t)
{
*t = 8;
}
输出是
Before update, 5
After update, 8
是不是可以说，在java里没有相应的功能？

null

【在 r******j 的大作中提到】

: 你所说的把最后一个设成null，只是把某一个指向最后一个node的reference设为null
: 了，还会有其他reference知道这个最后一个node在哪，比如previous node的next。你
: 只是杀了一个知道真相的目击证人，还有其他人也知道真相。。。
:
: list

l*i2013-02-15 08:02

13 楼

我觉得你的方法和我的基本一样，实际跑了一下，不行。
参见楼上的解释。
发信人: robertxj (robertxj), 信区: JobHunting
标题: Re: 如何删除 linked list 的最后一个元素 (转载)
发信站: BBS 未名空间站 (Sat Feb 16 20:11:27 2013, 美东)
你所说的把最后一个设成null，只是把某一个指向最后一个node的reference设为null
了，还会有其他reference知道这个最后一个node在哪，比如previous node的next。你
只是杀了一个知道真相的目击证人，还有其他人也知道真相。。。

【在 c*****a 的大作中提到】

: 这样算不算作弊......
: public void delete(ListNode node){
: if(node == null) return;
: while(node.next!=null){
: node.val=node.next.val;
: node=node.next;
: }
: node=null;
: }