python编程中实现linkedlist(链表)报错是因为什么,怎么解决?
发布网友
发布时间：2022-04-23 03:07
共3个回答
懂视网
时间：2022-04-12 21:38
2.1 Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? import java.util.LinkedList;import java.util.Iterator;import java.util.Collections;import jav
2.1 Write code to remove duplicates from an unsorted linked list.FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
import java.util.LinkedList;
import java.util.Iterator;
import java.util.Collections;
import java.util.Hashtable;
public class Solution{
//brute-force time complexity:O(n^2) space complexity:O(1)
public static void removeDuplicate1(LinkedList list){
for(int i=0;i < list.size()-1;i++)
for(int j=i+1;j < list.size();)
if(list.get(i) == list.get(j))
list.remove(j);
else
j++;
}
//could't keep order time complexity:O(nlogn) space complexity:O(1)
public static void removeDuplicate2(LinkedList list){
//sort
Collections.sort(list);
if(list.size() >= 2){
for(int i=0;i < list.size()-1;){
if(list.get(i) == list.get(i+1))
list.remove(i+1);
else
i++;
}
}
}
//1.keep order 2.time complexity:O(n) 3.space complexity:O(n): (worst case)
public static void removeDuplicate3(LinkedList list){
Hashtable hash = new Hashtable();
//lookup hashtable to delete repeat elements
for(int i=0;i < list.size();){
if(hash.containsKey(list.get(i)))
list.remove(i);
else{
hash.put(list.get(i), "");
i++;
}
}
}
private static void printLinkedList(LinkedList list){
Iterator it = list.iterator();
while(it.hasNext()){
System.out.print((Integer)it.next()+" ");
}
System.out.println();
}
public static void main(String[] args){
LinkedList list = new LinkedList();
list.add(6);list.add(2);list.add(2);list.add(3);
list.add(1);list.add(4);list.add(2);list.add(3);
list.add(7);list.add(2);list.add(2);list.add(10);
Solution.printLinkedList(list);
Solution.removeDuplicate3(list);
Solution.printLinkedList(list);
}
} 1.brute-force time complexity: O(n^2) space complxity:O(1), 输出元素保持原有顺序
2.sort：time complexity：O(nlogn) space complexity:O(1), 输出元素为排序后结果
3.hashtable：time complexity：O(n) space complexity:O(n), 输出元素保持原有顺序
类似问题:http://blog.csdn.net/u011559205/article/details/38125405
热心网友
时间：2022-04-12 18:46
楼主你好！
看你的代码存在很多问题，一个个来说明
1）首先你代码的报错源于你想用list来展开你的SLinkedList类，在python中，除非内置的可迭代对象外，其他都需要实现__iter__()函数，才能用list来进行展开。注意：判断一个对象是否可迭代，请使用isinstance(obj, Iterable)来判断obj是不是可以迭代，Iterable需要从collections中导入
2）插入的方法存在严重问题，按楼主的方法插入的话，因为头节点始终在变，所以当你需要遍历链表的时候就会找不到头节点；
3）pop的方法实现也有问题，因为是单向链，所以无法从末节点开始删除，只能删除头节点
4）top方法的意图未知
其他：
下面列举了一下我修改后的方案，做了一些锦上添花的操作，每个基本操作都会返回链表对象，这样就可以使用链式操作来写代码；迭代函数使用yield来实现，避免展开时占用不必要的内存。
另：我的展开时直接取链表中各个节点的元素，加了一些关键注释在代码中；
# -*- coding: utf-8 -*-class Node:
def __init__(self):
'''
elm:节点元素
nxt:下个节点指针
'''
self.elm, self.nxt = None, None
class SLinkedList:
def __init__(self):
'''
head: 链表头
end_point: 链表尾
'''
self.head = None
self.end_point = None
def push(self, x):
p = Node()
p.elm = x
if self.head is None:
self.head = p
self.end_point = p
return self
self.end_point.nxt = p
self.end_point = p
return self
def pop(self):
'''因为实现的是一个单链表，所以只能从头开始删除节点'''
if self.head.nxt is None:
return
self.head = self.head.nxt
return self
def __iter__(self):
temp_node = self.head
while temp_node is not None:
yield temp_node.elm
temp_node = temp_node.nxt
if __name__ == '__main__':
'''增加1,2,5三个元素，并删除一个头节点'''
mylinklist = SLinkedList().push(1).push(2).push(5).pop()
print(list(mylinklist))
其实python这个语言使用链表有些画蛇添足，但是如果拿来当作需求练手也无妨。
望采纳，谢谢！
热心网友
时间：2022-04-12 20:04
你得实现__iter__才能使用list直接列出元素。
