数据结构算法之链表

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

#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中的倒数第３个节点
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\n５是否存在与链表ln中:",end=" ")
if flag:
    print("Yes")
else:
    print("No")