python-单链表实现（oj向）

╰+攻爆jí腚メ 2022-12-27 09:00 148阅读 0赞

**目录**

前言

基本操作函数

添加

尾插

随意位置插

长度

查找

返回第一个找到的节点

统计个数

删除

按索引

按值

清空

显示

高级操作函数

返回倒数第k个节点（快慢指针）

全部代码

--------------------

# 前言 #

本文用python实现了单链表，由于博主是为了刷leetcode，熟悉python如何去实现数据结构与算法，所以采用的Solution方式，函数没有当做单链表类的方法。

单链表实现的是**带头结点**的单链表，头结点内的数据为**单链表的长度**。

**结构**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None

以上图展示基本操作函数

# 基本操作函数 #

## 添加 ##

### 尾插 ###

def append(self, head: ListNode, val) -> None:
            """
            add a node with val equal "val" to the end of List
            :param head: the head of List
            :param val: value of ListNode
            :return:None
            """
            cur = head
            while cur.next is not None:
                cur = cur.next
            cur.next = ListNode(val)
            head.val += 1
            return None

**作用**

在链表尾部添加一个节点，链表长度+1

**参数**

*  head：头结点
 *  val：待插入的值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 尾插1

同理，插入2和3，不再赘述

### 随意位置插 ###

def insert(self, head: ListNode, index: int, val) -> None:
            """
            insert a node at index of list
            :param head: the head of List
            :param index: the position where you want to insert after you insert
            :param val:
            :return:
            """
            cur = head
            if index < 0 or index > self.length(head):
                raise IndexError(f'{index} is out of index')
            i = 0
            while cur is not None:
                if i == index:
                    NewNode = ListNode(val)
                    NewNode.next = cur.next
                    cur.next = NewNode
                    head.val += 1
                    return None
                cur = cur.next
                i += 1
            return None

**作用**

在index处插入一个值为val的节点，即插入后index处节点值为val，之前的节点索引不变，之后的索引+1

**参数**

*  head：头结点
 *  index：值插入后的索引
 *  val：插入的节点的值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][] 位置插入

同理，再插入3。至此，链表内容为上面前言所示。

## 长度 ##

def length(self, head: ListNode) -> int:
            """
            :param head: the head of List
            :return: length of List
            """
            return head.val

**返回**

链表的长度

![长度][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2] 长度

## 查找 ##

### 返回第一个找到的节点 ###

def find(self, head: ListNode, val, begin=0):
            """
            find the first node with val equal "val", begin with "begin", include begin
            :param val:value of ListNode
            :param head: the head of List
            :param begin: the first position of List when looking for "val"
            :return: the first node with "val" and it's index/None,0
            """
            if begin < 0 or begin > self.length(head):
                raise IndexError(f'{begin} is out of index')
            cur = head.next
            i = 0
            while cur is not None:
                if i < begin:
                    i += 1
                    cur = cur.next
                    continue
                if cur.val == val:
                    return cur, i
                cur = cur.next
                i += 1
            return None, 0

**作用**

从单链表或单链表的子链表中查找值为val的节点

**参数**

*  head：头结点
 *  val：插入的节点的值
 *  begin：开始的节点索引（包含），默认为0，若填入>0且在有效范围内的数，则查找范围为\[begin，length)

**返回**

*  找到，返回节点指针和索引
 *  未找到，返回None和0

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3][] 查找

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 4][] 子链表查找

###  统计个数 ###

def count(self, head: ListNode, val, begin=0, end=None) -> int:
            """
            count how many val in List from "begin" to "end", including "begin","end" not included
            :param head: the head of List
            :param val: value of ListNode
            :param begin:  the first position of List when looking for "val"
            :param end:  the end position of List when looking for "val"
            :return: number of val in List
            """
            if begin < 0 or begin > self.length(head):
                raise IndexError(f'{begin} is out of index')
            if end is None:
                end = head.val
            if end < 0 or end > self.length(head):
                raise IndexError(f'{end} is out of index')
            if end < begin:
                raise ValueError(f'begin({begin}) must less than end({end}).')
            cnt = 0
            cur = head.next
            i = 0
    
            while cur is not None:
                if i == end:
                    break
                if i < begin:
                    i += 1
                    continue
                if cur.val == val:
                    cnt += 1
                cur = cur.next
                i += 1
            return cnt

**作用**

从单链表或单链表的子链表中统计值为val的节点个数

**参数**

*  head：头结点
 *  val：插入的节点的值
 *  begin：开始的节点索引（包含），默认为0
 *  end：结束的节点索引（不包含），默认为length

**返回**

值为val的节点个数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 5][] 整个链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 6][] 子链表

## 删除 ##

### 按索引 ###

def pop(self, head: ListNode, index: int = None) -> None:
            """
            remove the node at index of List, default: the last one
            :param head: the head of List
            :param index:  the position of node where you want to remove
            :return: None
            """
            i = 0
            if index is None:
                if head.val == 0:
                    raise IndexError('pop from empty list')
                index = head.val - 1
            else:
                if index < 0 or index > self.length(head):
                    raise IndexError(f'{index} is out of index.')
            cur = head
            while cur is not None:
                if i == index:
                    cur.next = cur.next.next
                    head.val -= 1
                    return None
                else:
                    cur = cur.next
                    i += 1
            return None

**作用**

删除索引为index的节点

**参数**

*  head：头结点
 *  index：待删除节点的索引，默认最后一个

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 7][] 按索引删除

### 按值 ###

def remove(self, head: ListNode, val) -> None:
            """
            remove all the node whose val equal "val"
            :param head: the head of List
            :param val: value of ListNode
            :return: None
            """
            cur = head
            while cur is not None and cur.next is not None:
                while cur.next.val == val:
                    cur.next = cur.next.next
                    head.val -= 1
                    if cur.next is None:
                        break
                cur = cur.next
            return None

**作用**

删除单链表中**所有**值为val的节点

**参数**

*  head：头结点
 *  val：待删除节点的值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 8][] 按值删除

### 清空 ###

def clear(self, head: ListNode) -> None:
            """
            clear the List
            :param head: the head of List
            :return: None
            """
            head.val = 0
            head.next = None
            return None

**作用**

清空链表，回到初始化状态

![20201211110349519.PNG][] 清空

## 显示 ##

def display(self, head: ListNode) -> None:
            cur = head.next
            print(f'List({head.val}):')
            while cur is not None:
                print(cur.val, end=' ')
                cur = cur.next
            print()
            return None

**作用**

打印链表长度和所有节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 9][] 打印

注意，此时已清空了链表，所以就没有了。

# 高级操作函数 #

## 返回倒数第k个节点（快慢指针） ##

def backword_k(self, head: ListNode, k: int) -> ListNode:
            """
            return the k node from behind
            :param k: a number, index from 1
            :param head: the head of List
            :return: the k node from behind
            """
            if head.val == 0:
                raise IndexError(f'list is empty.')
            if k < 1 or k > head.val:
                raise IndexError(f'{k} is out of index.')
            fast = head.next
            slow = head.next
            while k != 0:
                fast = fast.next
                k -= 1
            while fast is not None:
                fast = fast.next
                slow = slow.next
            return slow

**作用**

返回倒数第k个节点的指针

**参数**

*  head：头结点
 *  k：倒数第k个，符合正常人思维，倒数第1至倒数第length个

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 10][] 倒数第k个节点

# 全部代码 #

"""
    --coding:utf-8--
    @File: singly-linked list.py
    @Author:frank yu
    @DateTime: 2020.12.10 21:53
    @Contact: frankyu112058@gmail.com
    @Description:implement of singly-linked list with head node(the val of head node is length of list)
    """
    
    
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
    
    class Solution:
        # basic
        def length(self, head: ListNode) -> int:
            """
            :param head: the head of List
            :return: length of List
            """
            return head.val
    
        def display(self, head: ListNode) -> None:
            cur = head.next
            print(f'List({head.val}):')
            while cur is not None:
                print(cur.val, end=' ')
                cur = cur.next
            print()
            return None
    
        def find(self, head: ListNode, val, begin=0):
            """
            find the first node with val equal "val", begin with "begin", include begin
            :param val:value of ListNode
            :param head: the head of List
            :param begin: the first position of List when looking for "val"
            :return: the first node with "val" and it's index/None,0
            """
            if begin < 0 or begin > self.length(head):
                raise IndexError(f'{begin} is out of index')
            cur = head.next
            i = 0
            while cur is not None:
                if i < begin:
                    i += 1
                    cur = cur.next
                    continue
                if cur.val == val:
                    return cur, i
                cur = cur.next
                i += 1
            return None, 0
    
        def count(self, head: ListNode, val, begin=0, end=None) -> int:
            """
            count how many val in List from "begin" to "end", including "begin","end" not included
            :param head: the head of List
            :param val: value of ListNode
            :param begin:  the first position of List when looking for "val"
            :param end:  the end position of List when looking for "val"
            :return: number of val in List
            """
            if begin < 0 or begin > self.length(head):
                raise IndexError(f'{begin} is out of index')
            if end is None:
                end = head.val
            if end < 0 or end > self.length(head):
                raise IndexError(f'{end} is out of index')
            if end < begin:
                raise ValueError(f'begin({begin}) must less than end({end}).')
            cnt = 0
            cur = head.next
            i = 0
    
            while cur is not None:
                if i == end:
                    break
                if i < begin:
                    i += 1
                    continue
                if cur.val == val:
                    cnt += 1
                cur = cur.next
                i += 1
            return cnt
    
        def append(self, head: ListNode, val) -> None:
            """
            add a node with val equal "val" to the end of List
            :param head: the head of List
            :param val: value of ListNode
            :return:None
            """
            cur = head
            while cur.next is not None:
                cur = cur.next
            cur.next = ListNode(val)
            head.val += 1
            return None
    
        def insert(self, head: ListNode, index: int, val) -> None:
            """
            insert a node at index of list
            :param head: the head of List
            :param index: the position where you want to insert after you insert
            :param val:
            :return:
            """
            cur = head
            if index < 0 or index > self.length(head):
                raise IndexError(f'{index} is out of index')
            i = 0
            while cur is not None:
                if i == index:
                    NewNode = ListNode(val)
                    NewNode.next = cur.next
                    cur.next = NewNode
                    head.val += 1
                    return None
                cur = cur.next
                i += 1
            return None
    
        def pop(self, head: ListNode, index: int = None) -> None:
            """
            remove the node at index of List, default: the last one
            :param head: the head of List
            :param index:  the position of node where you want to remove
            :return: None
            """
            i = 0
            if index is None:
                if head.val == 0:
                    raise IndexError('pop from empty list')
                index = head.val - 1
            else:
                if index < 0 or index > self.length(head):
                    raise IndexError(f'{index} is out of index.')
            cur = head
            while cur is not None:
                if i == index:
                    cur.next = cur.next.next
                    head.val -= 1
                    return None
                else:
                    cur = cur.next
                    i += 1
            return None
    
        def remove(self, head: ListNode, val) -> None:
            """
            remove all the node whose val equal "val"
            :param head: the head of List
            :param val: value of ListNode
            :return: None
            """
            cur = head
            while cur is not None and cur.next is not None:
                while cur.next.val == val:
                    cur.next = cur.next.next
                    head.val -= 1
                    if cur.next is None:
                        break
                cur = cur.next
            return None
    
        def clear(self, head: ListNode) -> None:
            """
            clear the List
            :param head: the head of List
            :return: None
            """
            head.val = 0
            head.next = None
            return None
    
        # advanced
    
        def backword_k(self, head: ListNode, k: int) -> ListNode:
            """
            return the k node from behind
            :param k: a number, index from 1
            :param head: the head of List
            :return: the k node from behind
            """
            if head.val == 0:
                raise IndexError(f'list is empty.')
            if k < 1 or k > head.val:
                raise IndexError(f'{k} is out of index.')
            fast = head.next
            slow = head.next
            while k != 0:
                fast = fast.next
                k -= 1
            while fast is not None:
                fast = fast.next
                slow = slow.next
            return slow
    
    
    def menu():
        print('--------------------Menu--------------------')
        print('1.Add                2.Delete')
        print('3.Find               4.Count')
        print('5.Length             6.Show')
        print('7.Clear              8.the k node from behind')
        print('e.Exit')
    
    
    def menu_add():
        print('--------------------Add Menu--------------------')
        print('1.Append                2.Insert')
    
    
    def menu_delete():
        print('--------------------Delete Menu--------------------')
        print('1.Pop                2.Remove')
    
    
    def menu_find():
        print('--------------------Find Menu--------------------')
        print('1.find from whole List                2.find from sub List')
    
    
    def menu_count():
        print('--------------------Count Menu--------------------')
        print('1.count from whole List                2.count from sub List')
    
    
    if __name__ == '__main__':
        s = Solution()
        head = ListNode(0)
        while True:
            menu()
            choice = input('please select an option：')
            if choice == '1':
                menu_add()
                choice = input('please select an option：')
                if choice == '1':
                    val = input('please input the value of node:')
                    s.append(head, val)
                if choice == '2':
                    val = input('please input the position and value of node(split with white space):')
                    s.insert(head, int(val.split(' ')[0]), val.split(' ')[1])
                s.display(head)
                continue
            if choice == '2':
                menu_delete()
                choice = input('please select an option：')
                if choice == '1':
                    index = input('please input the index of node which need to be deleted:')
                    s.pop(head, int(index))
                if choice == '2':
                    val = input('please input the value of node:')
                    s.remove(head, val)
                s.display(head)
            if choice == '3':
                menu_find()
                choice = input('please select an option：')
                if choice == '1':
                    val = input('please input the value of node:')
                    node, index = s.find(head, val)
                    if node is None:
                        print(f'not find {val}.')
                    else:
                        print(f'find {node.val} at {index}.')
                if choice == '2':
                    param = input('please input the value and the beginning index split with white space:')
                    node, index = s.find(head, param.split(' ')[0], begin=int(param.split(' ')[1]))
                    if node is None:
                        print(f'not find {param.split(" ")[0]}.')
                    else:
                        print(f'find {node.val} at {index}.')
            if choice == '4':
                menu_count()
                choice = input('please select an option：')
                if choice == '1':
                    val = input('please input the value of node:')
                    cnt = s.count(head, val)
                    print(f'find {cnt} "{val}" in list.')
                if choice == '2':
                    param = input('please input the value、begin、end with white space, # meanings no need:')
                    val = param.split(' ')[0]
                    begin = param.split(' ')[1]
                    end = param.split(' ')[2]
                    cnt = 0
                    if begin == '#':
                        cnt = s.count(head, val, end=int(end))
                    if end == '#':
                        cnt = s.count(head, val, begin=int(begin))
                    if begin != '#' and end != '#':
                        cnt = s.count(head, val, begin=int(begin), end=int(end))
                    print(f'find {cnt} "{val}" in sub list.')
            if choice == '5':
                print(f'the length of list is {s.length(head)}')
            if choice == '6':
                s.display(head)
            if choice == '7':
                s.clear(head)
            if choice == '8':
                k = input('please input k:')
                node_k = s.backword_k(head, int(k))
                print(f'the k node from behind is {node_k.val}')
            if choice == 'e':
                break

未完待续...

更多python相关内容：[【python总结】python学习框架梳理][python_python]

本人b站账号:[lady\_killer9][lady_killer9]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221120/a02233abc9b444bc870e4f52425bd4cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/61cf16cee1964e939b4fb4a21bf589c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2]: /images/20221120/40c3e7d0489748159f2121f25185b1b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3]: /images/20221120/d5c527cffa754d1dbc68a4669af8a744.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 4]: /images/20221120/d5ea9ad167344cf6b38ed03e5ddbd8ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 5]: /images/20221120/582c7614f40641c5b4c3bdab77efc890.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 6]: /images/20221120/407398a55977406cbab123dd097233ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 7]: /images/20221120/05bdfdf29ddd4a2590964a7b41b01b25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 8]: /images/20221120/8a3e68aef873492087b6266952a85082.png
[20201211110349519.PNG]: /images/20221120/c6403b60754e4d74b0667d5b3ca6eb29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 9]: /images/20221120/620c65acfb0e488e9a4abb525ca88093.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 10]: /images/20221120/3370db6b24bf4941b53e4b3d0745d3c0.png
[python_python]: https://blog.csdn.net/lady_killer9/article/details/108763489
[lady_killer9]: https://space.bilibili.com/374432302