2. python实现单链表

1. 创建Node节点

  1. 初始化节点属性 数据域和下一个节点的指针域
  2. 设置data属性，更加pythonic写法，类方法加@property转化为属性使用
  3. 修改属性
  4. 同样实现下一个节点指针的属性和修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Node(object):
    """创建链表的Node节点"""
    def __init__(self, data, next_node=None):
        """
        Node节点初始化方法
        :param data: 存储的值
        :param next_node: 下一个节点指针
        """
        self.__data = data
        self.__next = next_node

    @property
    def data(self):
        """
        获取Node存储值
        :return: 当前节点存储的值
        """
        return self.__data

    @data.setter
    def data(self, data):
        """
        设置Node节点值
        :param data: 要设置的值
        """
        self.__data = data

    @property
    def next_node(self):
        """
        获取Node下一个节点指针
        :return: 下一个节点指针
        """
        return self.__next

    @next_node.setter
    def next_node(self, next_node):
        """
        Node下一个节点指针的修改方法
        :param next_node: 新的下一个节点指针
        """
        self.__next = next_node

2. 创建单链表及方法

这里实现的单链表操作方法有：

  1. 查找

    • 按值查找
    • 按索引查找节点

  2. 插入

    • 头结点插入指定值
    • 在链表指定节点后插入值为value的节点
    • 在链表指定节点之前插入值为value的节点

  3. 删除

    • 删除指定节点
    • 删除指定值的节点
    • 删除链表中倒数第n个节点

  4. 一般方法

    • 创建一个节点

    • 打印当前链表所有节点数据

  5. 常见单链表考点

    • 查找链表中间节点

    • 翻转相邻两个节点

    • 翻转链表
    • 检查链表是否有环

  1. 初始化单链表私有头结点属性

    1
    2
    3
    4
    class SingleLinkList(object):
        """单向链表类"""
        def __init__(self):
            self.__head = None

  1. 按值查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def find_by_value(self, value):
            """
            按照指定值在单向链表中查找
            :param value: 查找的指定值
            :return: node
            """
            node = self.__head
            while (node is not None) and (node.data != value):
                # 如果节点不为空且节点值不等于查找值就一直往后查找
                node = node.next_node
            return node

  1. 按索引查找节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def find_by_index(self, index):
            """
            按照指定索引在单向链表中查找
            :param index: 查找的指定索引
            :return: node
            """
            node = self.__head
            pos = 0
            while (node is not None) and (pos != index):
                # 如果节点不空且索引不是查找的，节点网后移一个，索引也往后移一个
                node = node.next_node
                pos += 1
            return node

  2. 头结点插入指定值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def insert_node_to_head(self, value):
            """
            链表头部插入值为value的节点
            :param value: 要插入的值
            """
            node = Node(value)
            #插入节点的下一个节点指向头, 头结点指向插入节点
            node.next_node = self.__head
            self.__head = node

  3. 在链表指定节点后插入值为value的节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def insert_after(self, node, value):
            """
            在链表指定节点后插入一个值为value的node
            :param node: 指定的节点
            :param value: 要插入的值
            """
            if node is None:  # 指定节点为空就什么都不做
                return

            new_node = Node(value)
            # 将指定节点的下一个节点指针赋值给新节点的下一个指针
            new_node.next_node = node.next_node
            # 新节点接到指定节点后
            node.next_node = new_node

  4. 在链表指定节点之前插入值为value的节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def insert_before(self, node, value):
            """
            在指定节点前插入值为value的节点
            :param node: 指定节点
            :param value: 插入的值
            """
            if (node is None) and (self.__head is None):
                # 如果指定节点是空或者空链表之前插入数据，则什么都不做
                return

            if node == self.__head:
                # 如果指定节点是头结点就直接用头结点插入
                self.insert_to_head(value)
                return
            new_node = Node(value)
            pos = self.__head  # 设置位置节点为头结点
            not_found = False  # 没找到标志位
            while pos.next_node != node:  # 寻找节点直到等于指定节点       
                if pos.next_node is not None:  # 如果当前位置的下一个节点不为空，继续后移位置
                    pos = pos.next_node
                else:  # 直到链表最后节点,没找到指定节点，将没找到标志位置为True，并跳出循环
                    not_found = True
                    break

            if not not_found:  # 找到指定节点的前节点就插入node
                pos.next_node = new_node
                new_node.next_node = node

  5. 删除指定节点，类似于7插入指定节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def delete_by_node(self, node):
            """
            删除链表指定节点
            :param node: 指定节点
            """
            if self.__head is None:  # 如果头结点为空，就不用删除直接返回
                return
            if node == self.__head:
                # 如果指定节点是头结点，直接将头结点接到节点下一个节点
                self.__head = node.next_node
                return

            pos = self.__head
            not_found = False
            while pos.next_node != node:
                if pos.next_node is not None:  # 如果当前位置的下一个节点不为空，继续后移到下一个位置
                    pos = pos.next_node
                else:  # 直到链表最后节点,没找到指定节点，将没找到标志位置为True，并跳出循环
                    not_found = True
                    break
            if not not_found:
                pos.next_node = node.next_node

  6. 删除指定值的节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    def delete_by_value(self, value):
            """
            删除链表中指定值节点
            :param value: 删除的指定值
            """
            if self.__head is None:
                return

            if self.__head.data == value:
                # 如果头节点值就等于删除值，直接将头结点指向下一个节点
                self.__head = self.__head.next_node

            pos = self.__head  # 位置位
            node = self.__head.next_node  # 第一个节点
            not_found = False
            while node.data != value:  # 节点值不为删除值
                if node.next_node is not None:  # 如果当前节点的下一个节点不为空，继续后移位置节点
                    pos = node
                    node = node.next_node
                else:  # 直到链表最后节点,没找到指定节点，将没找到标志位置为True，并跳出循环
                    not_found = True
                    break
            if not not_found:
                pos.next_node = node.next_node

  1. 删除链表中倒数第n个节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def delete_last_n_node(self, n):
           """
           删除链表中倒数第n个节点
           主体思路：
           设置快慢指针，快指针先行n步，然后快慢指针同时往后移，
           当快指针到链表尾部时，直接将这时慢指针的下一个节点接到第n个节点上
           :param n: 删除倒数第n个节点
           """
           fast = self.__head
           slow = self.__head
           step = 0
           while step <= n:
               fast = fast.next_node
               step += 1
        
           while fast.next_node is not None:
               tmp = slow
               fast = fast.next_node
               slow = slow.next_node
           tmp.next_node = slow.next_node

  1. 查找链表中间节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def find_mid_node(self):
            """
            查找链表中的中间节点
            主体思路，依旧是快慢指针，快指针走2步，慢指针走1步，
            当快指针到链表尾部时，慢指针刚好到中间
            :return: 中间节点
            """
            fast = self.__head
            slow = self.__head

            while fast.next_node is not None:
                fast = fast.next_node.next_node
                slow = slow.next_node
            return slow

  2. 创建一个节点

    1
    2
    3
    4
    5
    6
    7
    def create_node(self, value):
            """
            创建值为value的node
            :param value: 创建节点的值
            :return: 创建的节点
            """
            return Node(value)

  3. 打印当前链表所有节点数据

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def print_all(self):
            """
            打印当前链表所有节点数据
            """
            pos = self.__head
            if pos is None:
                print("当前链表为空")
                return

            while pos.next_node is not None:
                print(str(pos.data) + "-->", end="")
                pos = pos.next_node
            print(str(pos.data))

  4. 翻转相邻两个节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def __reversed_with_two_node(self, pre, node):
            """
            翻转相邻两个节点
            :param pre: 前一个节点
            :param node: 当前节点
            :return: (pre， node)
            """
            tmp = node.next_node
            node.next_node = pre
            pre = node  # 啰嗦点但更容易理解
            node = tmp
            return pre, node

  1. 翻转链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def reversed_list(self):
        """
            翻转链表
            """
        if self.__head is None or self.__head.next_node is None:
            # 链表为空或只有一个节点直接返回
            return

        pre = self.__head
        node = self.__head.next_node
        # 当下一个节点不为空，翻转两个节点
        while node is not None:
            pre, node = self.__reversed_with_two_node(pre, node)
            self.__head.next_node = None
            self.__head = pre

  1. 检查链表是否有环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def has_ring(self):
        """
            检查链表是否有环, 快慢指针相遇为环
            :return: True or False
            """
        fast = self.__head
        slow = self.__head

        while (fast is not None) and (fast.next_node is not None):
            # 注意一定要有fast的下一个节点也不空
            slow = slow.next_node
            fast = fast.next_node.next_node
            if fast == slow:
                return True
            return False

对上述代码进行测试如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
if __name__ == "__main__":
    l = SingleLinkList()
    for i in range(9):
        l.insert_node_to_head(i)
    l.print_all() #8-->7-->6-->5-->4-->3-->2-->1-->0
    node5 = l.find_by_value(5)
    print(node5.data) #5
    node6 = l.find_by_index(6)
    print(node6.data)#2
    l.insert_after(node5, 31)
    l.print_all() #8-->7-->6-->5-->31-->4-->3-->2-->1-->0
    l.insert_before(node5, 32)
    l.print_all() #8-->7-->6-->32-->5-->31-->4-->3-->2-->1-->0
    l.delete_by_node(node5) #删除指定节点5
    l.print_all() #8-->7-->6-->32-->31-->4-->3-->2-->1-->0
    l.delete_by_value(31) 
    l.print_all()#8-->7-->6-->32-->4-->3-->2-->1-->0
    l.delete_last_n_node(2)#删除倒数第2个节点
    l.print_all() #8-->7-->6-->32-->4-->2-->1-->0
    node_mid = l.find_mid_node()
    print(node_mid.data) #32
    create_node = l.create_node(99)
    l.insert_after(node5, create_node.data)
    l.print_all() #8-->7-->6-->32-->4-->2-->1-->0
    l.reversed_list()
    l.print_all() #0-->1-->2-->4-->32-->6-->7-->8
    has_ring = l.has_ring()
    print(has_ring) #False