一个关于单向链表的面试题。

lishengxu

晕了，那不是把链表结构都给改了么？？

1jjk

有改吗？

多了个域

langue

原帖由 lishengxu 于 2007-2-5 15:40 发表
晕了，那不是把链表结构都给改了么？？

原帖由 1jjk 于 2007-2-5 15:42 发表
有改吗？

多了个域

链表是一种数据结构，而数据结构是用来承载数据的。这里的 data 就是一个数据域

--

emacsnw

原帖由 1jjk 于 2007-2-4 23:42 发表
有改吗？

多了个域

我不认为可以这么做。假设公司仅仅要你效率高点的实现这么一个函数

1. 
   
2. struct Node *first_loop_node(struct Node *head);
   

复制代码

你可以随便改变struct Node的定义吗？呵呵。

lishengxu

我的意思是说节点那个结构体的结构不是改了么？
多了一个标志位对吧？若我不想改变原来节点的结构体呢？

1jjk

原帖由 emacsnw 于 2007-2-5 15:49 发表


我不认为可以这么做。假设公司仅仅要你效率高点的实现这么一个函数

1. 
   
2. struct Node *first_loop_node(struct Node *head);
   

复制代码

你可以随便改变struct Node的定义吗？呵呵。

前辈批评得是啊
可以自己定义一个数据结构吗？
跟着这个数据结构同时执行操作；
不过空间是个问题啦！
诶~~！

emacsnw

原帖由 1jjk 于 2007-2-4 23:51 发表



前辈批评得是啊
可以自己定义一个数据结构吗？
跟着这个数据结构同时执行操作；
不过空间是个问题啦！
诶~~！

汗，千万别叫我“前辈”，搞的巨有压力-_-

这个题O(n)时间和O(n)空间的算法是很trivial的，只要把依次遍历，把地址存入hash就行了，第一次出现重复的地址就是需要的解。不过我在想是否有O(1)空间的算法，有点类似以前用两个额外指针来判断链表是否存在环的方法。

langue

好，一个用内部方法，一个用外部方法。

1jjk

原帖由 emacsnw 于 2007-2-5 16:01 发表


汗，千万别叫我“前辈”，搞的巨有压力-_-

这个题O(n)时间和O(n)空间的算法是很trivial的，只要把依次遍历，把地址存入hash就行了，第一次出现重复的地址就是需要的解。

顶一下啊！

cjaizss

原帖由 emacsnw 于 2007-2-5 16:01 发表


汗，千万别叫我“前辈”，搞的巨有压力-_-

这个题O(n)时间和O(n)空间的算法是很trivial的，只要把依次遍历，把地址存入hash就行了，第一次出现重复的地址就是需要的解。不过我在想是否有O(1)空间的算法，有 ...

O(1)空间复杂度是不存在的，信息量不够。