#节点 class ListNode: def __init__(self,val = 0,next = None): self.val = val self.next = next #空链表 class LinkedList: def __init(self): self.head = None #根据data初始化一个新链表 def create(self,data): self.head = ListNode(0) cur = self.head for i in range(len(data)): node = ListNode(data[i]) cur.next = node cur = cur.next #求线性链表长度 def length(self): count = 0 cur = self.head while cur: count += 1 cur = cur.next return count #查找元素 def find(self,val): cur = self.head while cur: if val == cur.val return cur cur = cur.next return None #插入元素 ##头部插入元素 def inserFront(self,val): node = ListNode(val) node.next = self.head self.head = node ##尾部插入元素 def insertRear(self,val): node = ListNode(val) cur = self.head while cur.next: cur = cur.next cur.next = node ##中间插入元素 def insertInside(self,index,val): count = 0 cur = self.head while cur and count < index - 1: count += 1 cur = cur.next if not cur: return 'Error' node = ListNode(val) node.next = cur.next cur.next = node #改变元素 def change(self,index,val): count = 0 cur = self.head while cur and count < index: count += 1 cur = cur.next if not cur: return 'Error' cur.val = val #删除元素 ##删除头部元素 def removeFront(self): if self.head: self.head = self.head.next #删除尾部元素 def removeRear(self): if not self.head.next: return 'Error' cur = self.head while cur.next.next: cur = cur.next cur.next = None #中间删除元素 def removeInside(self,index): count = 0 cur = self.head while cur.next and count < index - 1: count += 1 cur = cur.next if not cur: return 'Error' del_node = cur.next cur.next = del_node.next return-1
707.设计链表
class ListNode: def __init__(self, x): self.val = x self.next = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 curr = self.head for i in range(index+1): curr = curr.next return curr.val def addAtHead(self, val: int) -> None: node = ListNode(0) self.head.val = val node.next = self.head self.head = node self.size += 1 def addAtTail(self, val: int) -> None: node = ListNode(val) curr = self.head while curr.next: curr = curr.next curr.next = node self.size += 1 def addAtIndex(self, index: int, val: int) -> None: if index > self.size: return if index < 0: index = 0 self.size += 1 curr = self.head for i in range(index): curr = curr.next node = ListNode(val) node.next = curr.next curr.next = node def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return self.size -= 1 curr = self.head for i in range(index): curr = curr.next curr.next = curr.next.next
206.反转链表
class Solution: def reverseList(self, head: ListNode) -> ListNode: cur = None pre = head while pre != None: next = pre.next pre.next = cur cur = pre pre = next return cur
203.移除链表元素
class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: cur = head # 有时候也可以改变head。 while cur and cur.next: if cur.next.val == val: cur.next = cur.next.next cur = cur.next return head
328.奇偶链表
class Solution: def oddEvenList(self, head: ListNode) -> ListNode: if not head: return head evenHead = head.next odd, even = head, evenHead while even and even.next: odd.next = even.next odd = odd.next even.next = odd.next even = even.next odd.next = evenHead return head