链表面试总结,使用python实现,参考:https://www.cnblogs.com/lixiaohui-ambition/archive/2012/09/25/2703195.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#coding:utf-8

# 定义链表
class ListNode:
def __init__(self):
self.data = None
self.pnext = None

# 链表操作类
class ListNode_handle:
def __init__(self):
self.cur_node = None

# 链表添加元素
def add(self,data):
ln = ListNode()
ln.data = data

ln.pnext = self.cur_node
self.cur_node = ln
return ln

# 打印链表
def prt(self,ln):
while ln:
print(ln.data,end=" ")
ln = ln.pnext
# 逆序输出
def _reverse(self,ln):
_list = []
while ln:
_list.append(ln.data)
ln = ln.pnext
ln_2 = ListNode()
ln_h = ListNode_handle()
for i in _list:
ln_2 = ln_h.add(i)
return ln_2

# 求链表的长度
def _length(self,ln):
_len = 0
while ln:
_len += 1
ln = ln.pnext
return _len

# 查找指定位置的节点
def _find_loc(self,ln,loc):
_sum = 0
while ln and _sum != loc:
_sum += 1
ln = ln.pnext
return ln.data

# 判断某个节点是否在链表中
def _exist(self,ln,data):
flag = False
while ln and data != ln.data:
ln = ln.pnext
return flag

# 创建链表
ln = ListNode()
ln_h = ListNode_handle()
a = [1,4,2,5,8,5,7,9]
for i in a:
ln = ln_h.add(i)

print("正序输出...")
ln_h.prt(ln)

print("\n\n逆序输出...")
ln_2 = ln_h._reverse(ln)
ln_h.prt(ln_2)

# 求链表ln的长度
length = ln_h._length(ln)
print("\n\nln的长度为:",length)

# 查找链表ln中的倒数第3个节点
data = ln_h._find_loc(ln,ln_h._length(ln)-3)
print("\n\n倒数第三个节点为:",data)

# 返回某个节点在链表中的位置
loc = ln_h._loc(ln,5)

# 判断某个节点是否在链表中
flag = ln_h._exist(ln,5)
print("\n\n5是否存在与链表ln中:",end=" ")
if flag:
print("Yes")
else:
print("No")

打开微信扫一扫,关注微信公众号【搜索与推荐Wiki】