# 手把手教你调试链表题 - 小白也能学会！

我是胖虎啊

发布于 2022-06-27 18:03:58

4190

发布于 2022-06-27 18:03:58

文章被收录于专栏：测试开发卷货

手把手教你调试链表题 - 小白也能学会！

写这篇文章的意义

大家有没有遇到过这些场景:

因为 python 的基础数据结构是没有链表的, 所以大家可能刚开始学习链表这一种新的数据结构时, 会稍显吃力.
看链表相关的文章会介绍一些概念, 看完后感觉懂了,一做链表的题, 然后毫无头绪可言...
在Leetcode做链表相关的题时, 靠画图写出了链表题的答案, 信心满满的点击提交, 结果报错了. 想调试一下错误, 却无从下手! 因为链表题和普通的算法题不一样, 不能直接将代码拷贝到本地, 然后调试一下胖虎在刚开始学习链表时走了很多的弯路, 希望大家避免这些坑

链表的重要性

链表也属于一种必备的数据结构, 类似于python的数组, 字典的重要性.
Leetcode有很多的链表题, 有一些公司的测开面试题出过链表的相关题
java有个经典题

问: 请你说下 LinkedeList和ArrayList的区别？

答: ArrayList是Array(动态数组)的数据结构，LinkedList是Link(链表)的数据结构

所以了解链表的基础知识对于熟悉其它知识的原理是有一定帮助的

链表基础知识

链表基础知识可以参考这篇文章, 讲得比较详细(为了不重复造轮子)

https://juejin.cn/post/6855865111354851335#heading-2

链表基础代码(Python3)

linked_struct.py 这是自定义的基础链表结构

class ListNode:  # 定义结点
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        return str(self.val)


class SingleLinkList:  # 定义链表结构
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def append(self, item):
        node = ListNode(item)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            # 找到链表的尾部
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def length(self) -> int:   # 获取链表长度
        count = 0
        cur = self.head
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def view_linklist(self):  # 遍历列表
        dummy = ListNode()
        dummy.next = self.head
        while dummy.next is not None:
            if dummy.next.next is None:
                print(dummy.next.val)
            else:
                print(dummy.next.val, end=" -> ")
            dummy = dummy.next

linked_test.py 这是上面自定义的基础链表结构的使用示例

from leetcode.linked_struct import ListNode
from leetcode.linked_struct import SingleLinkList

link_list = SingleLinkList()

# 定义6个链表结点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node6 = ListNode(6)

# 定义链表的头结点(head)
link_list.head = node1

# 自定义添加链表结点 - 第1种方式
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6

# 遍历链表, 输出元素
link_list.view_linklist() # 1 -> 2 -> 3 -> 4 -> 5 -> 6
print(link_list.length())  # 6

# 自定义添加链表结点 - 第2种方式
node7 = ListNode(7)
link_list.append(node7)
link_list.view_linklist() # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7


print(link_list.is_empty())  # False
print(link_list.length())  # 7