node = ListNode(10)
node不是对象本身，是对象的引用
对象存储在堆空间(heap space)上
堆空间 heap space
栈空间 stack space
区别于数据结构的 heap & stack
引用的赋值
node1 = ListNode(10)
node2 = ListNode(20)
这里有两个对象，node1和node2是这两个对象的引用
node1 = node2，两个引用同时指向一个对象
引用的好处与用处
引用也存的是数据，存的是指向这个对象的地址
使得数据更加整齐
需要专递引用去修改数据
数据结构
存储数据的功能，组织排列存储数据，查询添加删除维护存在的数据
链表
由节点构成的列表，线性的数据结构
class ListNode:
def __init__(self, value):
self.val = value
self.next = None
def __str__(self):
return "{val:%s, next:%s}" % (self.val, self.next)
l1 = ListNode(5)
l2 = ListNode(8)
l3 = ListNode(10)
l4 = ListNode(12)
l5 = ListNode(22)
l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l5
print(l1)
LinkedList:5->8->10->12->22->null
基于ListNode实现一个Linked List
dummy Node 哨兵节点
dummyNode -> null
使得每一个元素都有前驱节点
class Node:
'''链表的节点'''
def __init__(self, item):
self.item = item
self.next = None
class SingleLinkList(object):
"""单链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 初始指针指向head
cur = self._head
count = 0
# 指针指向None 表示到达尾部
while cur is not None:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
"""遍历链表"""
# 获取head指针
cur = self._head
# 循环遍历
while cur is not None:
# 返回生成器
yield cur.item
# 指针下移
cur = cur.next
def add(self, item):
"""向链表头部添加元素"""
node = Node(item)
# 新结点指针指向原头部结点
node.next = self._head
# 头部结点指针修改为新结点
self._head = node
def append(self, item):
"""尾部添加元素"""
node = Node(item)
# 先判断是否为空链表
if self.is_empty():
# 空链表，_head 指向新结点
self._head = node
else:
# 不是空链表，则找到尾部，将尾部next结点指向新结点
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, index, item):
"""指定位置插入元素"""
# 指定位置在第一个元素之前，在头部插入
if index <= 0:
self.add(item)
# 指定位置超过尾部，在尾部插入
elif index > (self.length() - 1):
self.append(item)
else:
# 创建元素结点
node = Node(item)
cur = self._head
# 循环到需要插入的位置
for i in range(index - 1):
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除节点"""
cur = self._head
pre = None
while cur is not None:
# 找到指定元素
if cur.item == item:
# 如果第一个就是删除的节点
if not pre:
# 将头指针指向头节点的后一个节点
self._head = cur.next
else:
# 将删除位置前一个节点的next指向删除位置的后一个节点
pre.next = cur.next
return True
else:
# 继续按链表后移节点
pre = cur
cur = cur.next
def find(self, item):
"""查找元素是否存在"""
return item in self.items()
if __name__ == '__main__':
link_list = SingleLinkList()
for i in range(5):
link_list.append(i)
link_list.add(6)
for i in link_list.items():
print(i, end='\t')
link_list.insert(3, 9)
print('\n', list(link_list.items()))
link_list.remove(0)
print(link_list.find(4))
class Node:
'''链表的节点'''
def __init__(self, item):
self.item = item
self.next = None
class SingleCycleLinkList(object):
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 链表为空
if self.is_empty():
return 0
# 链表不为空
count = 1
cur = self._head
while cur.next != self._head:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
""" 遍历链表 """
# 链表为空
if self.is_empty():
return
# 链表不为空
cur = self._head
while cur.next != self._head:
yield cur.item
cur = cur.next
yield cur.item
def add(self, item):
""" 头部添加结点"""
node = Node(item)
if self.is_empty(): # 为空
self._head = node
node.next = self._head
else:
# 添加结点指向head
node.next = self._head
cur = self._head
# 移动结点，将末尾的结点指向node
while cur.next != self._head:
cur = cur.next
cur.next = node
# 修改 head 指向新结点
self._head = node
def append(self, item):
"""尾部添加结点"""
node = Node(item)
if self.is_empty(): # 为空
self._head = node
node.next = self._head
else:
# 寻找尾部
cur = self._head
while cur.next != self._head:
cur = cur.next
# 尾部指针指向新结点
cur.next = node
# 新结点指针指向head
node.next = self._head
def insert(self, index, item):
""" 指定位置添加结点"""
if index <= 0: # 指定位置小于等于0，头部添加
self.add(item)
# 指定位置大于链表长度，尾部添加
elif index > self.length() - 1:
self.append(item)
else:
node = Node(item)
cur = self._head
# 移动到添加结点位置
for i in range(index - 1):
cur = cur.next
# 新结点指针指向旧结点
node.next = cur.next
# 旧结点指针 指向 新结点
cur.next = node
def remove(self, item):
""" 删除一个结点 """
if self.is_empty():
return
cur = self._head
pre = Node
# 第一个元素为需要删除的元素
if cur.item == item:
# 链表不止一个元素
if cur.next != self._head:
while cur.next != self._head:
cur = cur.next
# 尾结点指向 头部结点的下一结点
cur.next = self._head.next
# 调整头部结点
self._head = self._head.next
else:
# 只有一个元素
self._head = None
else:
# 不是第一个元素
pre = self._head
while cur.next != self._head:
if cur.item == item:
# 删除
pre.next = cur.next
return True
else:
pre = cur # 记录前一个指针
cur = cur.next # 调整指针位置
# 当删除元素在末尾
if cur.item == item:
pre.next = self._head
return True
def find(self, item):
""" 查找元素是否存在"""
return item in self.items()
if __name__ == '__main__':
link_list = SingleCycleLinkList()
print(link_list.is_empty())
for i in range(5):
link_list.add(i)
print(list(link_list.items()))
for i in range(6):
link_list.append(i)
print(list(link_list.items()))
link_list.insert(3, 45)
print(list(link_list.items()))
link_list.remove(5)
print(list(link_list.items()))
print(4 in link_list.items())
翻转链表
1->2->3->null 3->2->1->null
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution(ListNode):
def reversed(self, head):
if not head or not head.next:
return head
curr = head
prev = None
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
def __str__(self):
return "{val:%s, next:%s}" % (self.val, self.next)
s1 = Solution(1)
s2 = Solution(2)
s3 = Solution(3)
s1.next = s2
s2.next = s3
print(s1.reversed(s1))
删除链表中的第n个节点
Input: list = 1->2->3->4->5->null， n = 2
Output: 1->2->3->5->null
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution(ListNode):
def removeNthFromEnd(self, head, n):
res = ListNode(0)
res.next = head
tmp = res
for i in range(0, n):
head = head.next
while head != None:
head = head.next
tmp = tmp.next
tmp.next = tmp.next.next
return res.next
def __str__(self):
return "{val:%s, next:%s}" % (self.val, self.next)
s1 = Solution(1)
s2 = Solution(2)
s3 = Solution(3)
s4 = Solution(4)
s5 = Solution(5)
s1.next = s2
s2.next = s3
s3.next = s4
s4.next = s5
print(s1.removeNthFromEnd(s1, 2))
网友评论