Python 链表笔记_python listnode是哪个库(1)_python listnode(0)

class MyLinkedList:
    def \_\_init\_\_(self):
        self.size = 0 # 记录链表节点数
        self.head = ListNode(0) # 定义一个 伪头节点

1
2
3
4
5

这里使用伪头部节点，来使得当链表为空和不为空操作一样。这个时候对于链表的索引与长度记录有了困惑。
问：对于一个有头部伪节点的链表，它的索引范围是多少？
原链表 3->2->1->Null
索引 [0, 1, 2] 长度 3
有伪头节点链表 0->3->2->1->Null
索引 [0, 1, 2, 3] 长度 4

在索引处添加节点

    def addAtIndex(self, index: int, val: int) -> None:   
        if index > self.size: return # 超过索引，不添加; 如果等于长度，则在尾部添加
        if index < 0: index = 0 # 要求小于0 就在头部添加节点

        to_add = ListNode(val)
        curr = self.head  # 伪头节点
        # 0，... ，index-1
        for _ in range(index):
            # 指向下一节点，等同于指向索引节点，最大的索引= 长度-1
            curr = curr.next
        # 添加操作
        to_add.next = curr.next
        curr.next = to_add
        # 记录链表长度的变化
        self.size += 1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

以上是十分关键的操作，有了这一步，在头部添加节点和在尾部添加节点功能调用这个函数就可以了。
接下来是获取 index 的值和在尾部添加节点，这里也有一些困惑：
获取 index 的值的for循环需要index + 1，而 在尾部添加节点 不需要，直接index，看看有啥差别？

获取 index 的值

因为这里的索引依旧是原链表的索引，不需要考虑加了伪头节点的链表。

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        curr = self.head
        for _ in range(index+1): # 例子：index=0
            curr = curr.next
        return curr.val

1
2
3
4
5
6
7
8

删除索引处节点

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size: return # 为啥是index >= self.size
        self.size -= 1
        pre = self.head
        for _ in range(index): # 指针指向它的前一个节点
            pre = pre.next
        curr = pre.next
        pre.next = curr.next

1
2
3
4
5
6
7
8
9

我们的目标是当前节点，拜拜了~
综上，问题解决。

报错

AttributeError: ‘NoneType’ object has no attribute ‘val’

通过检查，发现索引超过范围，但是还是调用了curr.next，细想一下，None怎么会有next 或者val的属性？
解决方法：检查索引范围设定。

链表相关题型

移除元素

在链表中删除节点，就要知道删除的节点的前一个节点。对于头节点来说，它没有前一个节点，为了方便编程，添加一个伪头节点，让头节点的操作与其他节点的操作一样，是一个不错的方法。

# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
    	# 伪头节点 
        dummy = ListNode(next=head)
        cur = dummy
        while (cur.next!=None):
            if cur.next.val==val:
                # 删除操作
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

反转链表

206.反转链表

初始化

        pre = None
        cur = head

1
2
3

迭代过程，记录当前结点cur，前一结点pre，后一结点nextt

        while cur!=None:
            nextt = cur.next


现在能在网上找到很多很多的学习资源，有免费的也有收费的，当我拿到1套比较全的学习资源之前，我并没着急去看第1节，我而是去审视这套资源是否值得学习，有时候也会去问一些学长的意见，如果可以之后，我会对这套学习资源做1个学习计划，我的学习计划主要包括规划图和学习进度表。



分享给大家这份我薅到的免费视频资料，质量还不错，大家可以跟着学习

![](https://img-blog.csdnimg.cn/img_convert/21b2604bd33c4b6713f686ddd3fe5aff.png)



**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**

**[需要这份系统化学习资料的朋友，可以戳这里无偿获取](https://bbs.csdn.net/topics/618317507)**

**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19