数据结构和算法-链表
2020-12-10 03:17
标签：循环链表 class 链表是否有环 append data 数据结构与算法 连续 false 依次 循环链表 双向循环链表 数组的缺点是大小固定, 一旦声明长度就要占用连续的内存空间, 当空间不够用时更换更大的空间, 此时就需要将原数组的所有数据迁移过去, 比较费时. 链表则可以动态扩容. 数组在查询上可以更快, 链表在插入和删除上更快, 为了结合数组和链表的优点, 有同时使用的情况, 比如一个网站的用户注册, 可以以 定义两个游标first和later, first步长是1, later步长是2. 同时向前走, 如果有环一定会遇到. 复杂度O(n) 定义两个指针first, later都初始化指向头节点, 然后first先走k步, 再同时走, 当first到尾节点的时候, 读出later节点的值. 复杂度是O(n) 我们说空间复杂度的时候, 是指除了原本的数据存储空间外, 算法还需要的额外的存储空间, 即不管原来所占空间是多少 数据结构和算法-链表 标签：循环链表 class 链表是否有环 append data 数据结构与算法 连续 false 依次 原文地址：https://www.cnblogs.com/zlone/p/10993902.html链表分类
优势:
当要处理的数据具有环形结构的时候, 适合循环链表. 如约瑟夫环问题A-Z为数组, 在每个字母后面加入链表, 这样可以在添加新用户的时候能快速找到要添加的链表并进行插入, 同时在查询用户的时候也能缩短查询时间常见边界条件
常见问题
单向链表
"""
单链表
"""
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next_ = next_
class SingleLinkedList(object):
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def size(self):
current = self.head
num = 0
while current != None:
current = current.next_
num += 1
return num
def prepend(self, value):
"""
在头部添加节点
:param value:
:return:
"""
self.head = Node(value, self.head)
def append(self, value):
"""
在尾部追加节点
:param value:
:return:
"""
node = Node(value)
if self.is_empty():
self.head = node
else:
current = self.head
while current.next_ != None:
current = current.next_
current.next_ = node
def insert(self, position, value):
"""
指定位置插入节点, 从1开始计数
:param position:
:param value:
:return:
"""
if position self.size():
self.append(value)
else:
node = Node(value)
tmp_pos = 1
pre_node = None
current = self.head
while tmp_pos 单链表反转
# coding:utf-8
"""
单链表反转
"""
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next_ = next_
def reverse(linked_list):
head = linked_list
pre = None
while head != None:
current = head
head = current.next_
current.next_ = pre
pre = current
return pre
def output(linked_list):
current = linked_list
res = []
while current != None:
res.append(current.data)
current = current.next_
print(res)
if __name__ == '__main__':
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
output(link)
root = reverse(link)
output(root)
"""
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
"""
链表成对调换
# coding:utf-8
"""
链表成对调换
1 -> 2 -> 3 -> 4
调换后为
2 -> 1 -> 4 -> 3
"""
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next_ = next_
def swap(head):
if head != None and head.next_ != None:
after = head.next_
head.next_ = swap(after.next_)
after.next_ = head
return after
return head
def output(linked_list):
current = linked_list
res = []
while current != None:
res.append(current.data)
current = current.next_
print(res)
if __name__ == '__main__':
link = Node(1, Node(2, Node(3, Node(4))))
output(link)
print('----')
link1 = swap(link)
output(link1)
"""
[1, 2, 3, 4]
----
[2, 1, 4, 3]
"""
判断是否交叉链表
sub_size
sub_size步
时间复杂度O(m+n)判断链表是否有环
# -*- coding:utf-8 -*-
"""
判断链表是否有环
"""
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next_ = next_
def check(head):
current1 = current2 = head
while True:
current1 = current1.next_ # 指向第一个节点
current2 = current2.next_.next_ # 指向第二个节点
if (not current1) or (not current2):
break
if current1.data == current2.data:
return True
return False
if __name__ == '__main__':
node1 = Node(6)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node1.next_ = node2
node2.next_ = node3
node3.next_ = node4
node4.next_ = node5
node5.next_ = node6
node6.next_ = node3 # 环交点
assert check(node1) == True
查找单链表倒数第k个元素
# -*- coding:utf-8 -*-
"""
找到链表的倒数第K个元素
定义两个游标, 第二个游标先走k-1步, 之后再同时走, 此时第一个游标停留位置就是倒数第K个元素
"""
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next_ = next_
def find_reverse_k(head, k):
c1 = head
current = head
for _ in range(k - 1):
current = current.next_
c2 = current
while c2.next_ != None:
c2 = c2.next_
c1 = c1.next_
return c1.data
if __name__ == '__main__':
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
assert find_reverse_k(link, 3) == 7
assert find_reverse_k(link, 1) == 9
assert find_reverse_k(link, 2) == 8
合并两个有序链表
# coding:utf-8
"""
合并两个有序单链表
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
"""
class Node(object):
def __init__(self, data, next_=None):
self.data = data
self.next_ = next_
def merge2linkedlist(l1, l2):
"""
合并两个有序链表
:param l1:
:param l2:
:return:
"""
if l1 == None and l2 == None:
raise Exception("None!!!")
if l1 == None:
return l2
if l2 == None:
return l1
# 使用head为辅助节点
head = Node(0)
current = head
while l1 and l2:
if l1.data l2.data:
current.next_ = l2
l2 = l2.next_
current = current.next_
if l1:
current.next_ = l1
if l2:
current.next_ = l2
return head.next_
if __name__ == "__main__":
l1 = Node(1, Node(2, Node(4)))
l2 = Node(1, Node(3, Node(4)))
tmp = merge2linkedlist(l1, l2)
res = []
while tmp:
res.append(tmp.data)
tmp = tmp.next_
print(res)
"""
[1, 1, 2, 3, 4, 4]
"""合并K个有序单链表
把K个链表2个为一组进行合并, 不断分组, 最后合并为一个有序链表
遍历所有链表将所有元素放在一个数组中, 然后对数组进行排序, 最后生成一个有序链表.
时间复杂度:
如果所有链表共有n个元素, 遍历需要O(n), 对数组排序需要O(nlogn), 最后连接O(n). 所以总的复杂度是O(n + nlogn + n), 也就是O(nlogn)注意
资料
上一篇：算法——帕斯卡三角
下一篇：C++--类的静态成员变量