1. 构建一个节点类
- class Node(object):
- def __init__(self, val):
- self.val = val
- self.next = None
- def __repr__(self):
- return "<val:{}>".format(self.val)
2. 构建一个单链表类
- class SimpleLinks(object):
- def __init__(self):
- self.head = None
- self.size = 0
- def __repr__(self):
- current = self.head
- res_views = []
- while current:
- res_views.append(current)
- current = current.next
- return "{}".format(res_views)
3. 从左边添加元素
- def appendLeft(self, val):
- node = Node(val)
- cur = node
- cur.next = self.head
- self.head = cur
- self.size += 1
4. 从右边添加元素
- def append(self, val):
- node = Node(val)
- if self.isEmpty():
- self.head = node
- else:
- cur = self.head
- while cur.next:
- cur = cur.next
- cur.next = node
- self.size += 1
5. 删除某个元素
- def delete(self, val):
- current = self.head
- pre = None
- while current:
- if current.val==val:
- if not pre:
- self.head = current.next
- else:
- pre.next = current.next
- self.size -= 1
- pre = current
- current = current.next
6. 查找元素值是否存在
- def isExist(self, val):
- isFound = False
- cur = self.head
- while cur:
- if cur.val == val:
- isFound = True
- break
- cur = cur.next
- return isFound
全部代码
- # -*-coding:utf-8-*-
- # Author:Lai
- # 链表
- import random
- from pprint import pprint
- class Node(object):
- def __init__(self, val):
- self.val = val
- self.next = None
- def __repr__(self):
- return "<val:{}>".format(self.val)
- class SimpleLinks(object):
- def __init__(self):
- self.head = None
- self.size = 0
- def __repr__(self):
- current = self.head
- res_views = []
- while current:
- res_views.append(current)
- current = current.next
- return "{}".format(res_views)
- def appendLeft(self, val):
- node = Node(val)
- cur = node
- cur.next = self.head
- self.head = cur
- self.size += 1
- def isEmpty(self):
- return self.size==0
- def append(self, val):
- node = Node(val)
- if self.isEmpty():
- self.head = node
- else:
- cur = self.head
- while cur.next:
- cur = cur.next
- cur.next = node
- self.size += 1
- def delete(self, val):
- current = self.head
- pre = None
- while current:
- if current.val==val:
- if not pre:
- self.head = current.next
- else:
- pre.next = current.next
- self.size -= 1
- pre = current
- current = current.next
- def isExist(self, val):
- isFound = False
- cur = self.head
- while cur:
- if cur.val == val:
- isFound = True
- break
- cur = cur.next
- return isFound
- def insert(self, pos, val):
- if pos <= 0:
- self.appendLeft(val)
- elif pos> self.size:
- self.append(val)
- else:
- node = Node(val)
- cur = self.head
- pre = None
- count = 0
- while count <pos:
- nextnode = cur.next
- pre = cur
- cur = nextnode
- count += 1
- pre.next = node
- node.next = cur
- def search_index(self, val):
- cur = self.head
- pre = None
- count = 0
- while cur:
- if cur.val == val:
- break
- cur = cur.next
- count += 1
- return count
- def reversedLinks(links):
- current = links.head
- pre = None
- while current:
- nextnode = current.next
- current.next = pre
- pre = current
- current = nextnode
- return pre
- def combineLinks(a_links, b_links):
- new_links = SimpleLinks()
- a_current = a_links.head
- b_current = b_links.head
- while a_current and b_current:
- if a_current.val> b_current.val:
- new_links.append(b_current.val)
- b_current = b_current.next
- else:
- new_links.append(a_current.val)
- a_current = a_current.next
- if a_current:
- while a_current:
- new_links.append(a_current.val)
- a_current = a_current.next
- else:
- while b_current:
- new_links.append(b_current.val)
- b_current = b_current.next
- return new_links
- def _mergeSort(a_list, b_list):
- a, b = 0, 0
- res_list = []
- while a <len(a_list) and b < len(b_list):
- if a_list[a] < b_list[b]:
- res_list.append(a_list[a])
- a += 1
- else:
- res_list.append(b_list[b])
- b += 1
- if a < len(a_list):
- res_list.extend(a_list[a:])
- else:
- res_list.extend(b_list[b:])
- return res_list
- # array = [1_list ,2_list, 3_list...]
- def combine(array):
- length = len(array) - 1
- a_list = []
- while length>= 0:
- b_list = array[length]
- res = _mergeSort(a_list, b_list)
- a_list = res
- length -= 1
- return a_list
- def cutList(array, n):
- for i in range(0, len(array), n):
- yield array[i:i+n]
- if __name__ == "__main__":
- pass
来源: http://www.bubuko.com/infodetail-2985413.html