class Node(object):
__slots__ = ['val', 'next']
def __init__(self, val, next=None):
self.val = val
self.next = next
class SingleLinkedList(object):
"""单向链表结构实现"""
def __init__(self):
self._head = None # 第一个元素指针
self._last = None # 最后一个元素指针
self._size = 0
def __str__(self):
"""完整的打印链表结构"""
arr = []
current = self._head
while current is not None:
arr.append(str(current.val))
current = current.next
return "{0}({1})".format(__class__, "=>".join(arr))
def __len__(self):
"""返回链表大小"""
return self._size
def is_empty(self):
"""链表是否为空"""
return self._head is None
def append(self, val):
"""链表末尾增加元素"""
node = Node(val)
if self.is_empty():
self._head = node
self._last = node
else:
self._last.next = node
self._last = node
self._size += 1
def add(self, val):
"""链表首部增加元素"""
node = Node(val)
if self.is_empty():
self._head = node
self._last = node
else:
node.next = self._head
self._head = node
self._size += 1
def insert(self, pos, val):
"""固定位置插入元素"""
node = Node(val)
if pos <= 0:
self.add(val)
elif pos >= self._size:
self.append(val)
else:
count = 1
pre = self._head
current = self._head.next
while current is not None:
if count == pos:
pre.next = node
node.next = current
else:
current = current.next
count += 1
self._size += 1
def index(self, val):
"""返回某个值的索引，未找到返回-1"""
index = 0
current = self._head
while current is not None:
if current.val == val:
return index
else:
current = current.next
index += 1
return -1
def get(self, index):
"""根据索引返回节点"""
count = 0
current = self._head
if index < 0 or index >= self._size:
raise Exception("IndexError: list index out of range")
while current is not None:
if count == index:
return current
else:
current = current.next
count += 1
def remove(self, val):
"""删除某个值"""
index = 0
pre = None
current = self._head
while current is not None:
if current.val == val:
if pre is None:
self._head = self._head.next
else:
pre.next = current.next
self._size -= 1
return
else:
pre = current
current = current.next
index += 1
raise Exception("ValueError: remove(x): x not in list")
def clear(self):
"""清空链表"""
self._head = None
self._size = 0
self._last = None
def pop(self, pos):
"""根据索引删除元素并返回"""
count = 0
pre = None
current = self._head
if pos < 0 or pos >= self._size:
raise Exception("IndexError: pop index out of range")
while current is not None:
if count == pos:
if pre is None:
self._head = self._head.next
else:
pre.next = current.next
self._size -= 1
return current
else:
pre = current
current = current.next
count += 1
def reverse(self):
"""反转链表结构"""
if self._size <= 1:
return self
pre = self._head
current = self._head.next
pre.next = None
self._last = pre
while current is not None:
next_node = current.next
if next_node is None:
# 到最后了，末尾元素变第一
self._head = current
print(self)
current.next = pre
pre = current
current = next_node
if __name__ == '__main__':
s = SingleLinkedList()
print(s.is_empty())
for i in range(10):
s.append(i)
print("append 1~10", s)
print("size: ", len(s))
print("index(3)", s.index(3))
# print("index(13)", s.index(13))
print("get(3)", s.get(3), s.get(3).val)
# print("get(13)", s.get(13))
print("pop(9)", s.pop(9).val, s)
print("pop(5)", s.pop(5).val, s)
print("size: ", len(s))
print("remove(6)", s.remove(6), s)
print("remove(0)", s.remove(0), s)
print("size: ", len(s))
print("s.reverse()", s.reverse(), s)
s.add(-1)
print("add(-1)", s)
s.add(-2)
print("add(-2)", s)
s.append(0)
print("append(0)", s)
print("size: ", len(s))
s1 = SingleLinkedList()
print("s1: ", s1)
s1.insert(1, 1)
print("insert(1,1)", s1)
s1.insert(2, 2)
print("insert(2,2)", s1)
s1.insert(1, 3)
print("insert(1,3)", s1)
s1.insert(0, 4)
print("insert(1,3)", s1)
链表结构练习题：
https://leetcode-cn.com/problems/add-two-numbers/
image.png
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = result = ListNode(0)
t = 0
while l1 is not None or l2 is not None:
if l1 is not None:
t += l1.val
l1 = l1.next
if l2 is not None:
t += l2.val
l2 = l2.next
result.next = ListNode(t % 10)
result = result.next
t = t // 10
# 最后一位的时候如果大于0需要进1
if t > 0:
result.next = ListNode(t)
return head.next
if __name__=='__main__':
s = Solution()
l1 = ListNode(3)
l2 = ListNode(4, next=l1)
l3 = ListNode(2, next=l2)
l4 = ListNode(4)
l5 = ListNode(6, next=l4)
l6 = ListNode(5, next=l5)
L1 = l3
L2 = l6
r = s.addTwoNumbers(L1, L2)
c = r
while c is not None:
print(c.val, end='')
c = c.next
