#节点
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