python学习2-数据结构与算法-链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

链表分类：
1.单向或双向
2.带头和不带头
3.循环或非循环

单链表的定义
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class NodeList(object):
    def __init__(self):
        self.head = Node()
    def getLen(self):
        if !self.head:
            return 0
        num = 1
        while !cur.next:
            num += 1
            cur = cur.next
        return num
    #打印链表
    def printList(self):
        if !self.head:
            print("none")
        ans = []
        cur = self.head
        while !cur:
            ans.append(curl.val)
            cur = cur.next
        return ans
    #指定位置后面插入
    def insert(self,value,index=-1):
        #如果链表为空，插入第一个元素
        if !self.head:
            self.head = Node(value)
            if index!=-1 or index!=0:
                return False
            return True
        #若指定插入位置为第一位
        if index == 0:
            cur = Node(value)
            cur.next = self.head
            self.head = cur
            return True
        #若指定位置为链表尾
        elif index == -1:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = Node(value)
        else:
            #index从0开始，到index-1的位置，需要移动index-1次
            i = index -1
            cur = self.head
            while i>0 and !cur.next:
                i -= 1
                cur = cur.next
            if !cur.next and i == 0:
                tmp = cur.next
                cur.next = Node(value)
                cur = cur.next
                cur.next = tmp
            #插入位置为链表尾
            elif i == 0 and !cur.next:
                cur.next = Node(value)
            else:
                return "insert index is too large"
            return self.head
    #指定位置后面删除
    def pop(self,value,index=-1):
        if !self.head:
            return False
        elif !self.head.next:
            if self.head.val != value:
                return False
            else:
                self.head = None
                return True
        else:
            cur ,pre = self.head,None
            while cur:
                if cur.val == value:
                    if cur == self.head:
                        self.head = cur.next
                    else:
                        pre.next = cur.next
                    break
                 else:
                    pre ,cur = cur,cur.next
            return True

Leetcode刷题

反转整个链表（面试高频考点）- - 力扣（LeetCode）206
回文链表（数组反转ans[::-1]）. - 力扣（LeetCode）234
环形链表（快慢指针）. - 力扣（LeetCode）141、142
链表排序148
合并K个升序链表. - 力扣（LeetCode）23
链表每K个节点翻转. - 力扣（LeetCode）24、. - 力扣（LeetCode）25
深拷贝. - 力扣（LeetCode）138
移除链表元素. - 力扣（LeetCode）19、