Python编程题50--设计单链表

2022-01-30  本文已影响0人  wintests

题目

单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针或引用。

请设计一个单链表,并在链表类中实现下列操作:

说明:链表节点的索引 index 是从 0 开始计算,比如链表中索引 1 下的节点,指的是链表中的第二个节点。

代码实现

class ListNode:  # 定义单链表
    def __init__(self, val=0, next=None):
        self.val = val  # 链表节点上存储的元素
        self.next = next  # 指向下一个链表节点


class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode(0)  # 定义虚拟头节点
        self.length = 0  # 定义链表的长度

    def get(self, index: int) -> int:
        if 0 <= index < self.length:
            cur = self.dummy_head
            cur = cur.next  # 因为多了一个虚拟头节点,所以需提前移动1位
            while index:  # 循环操作,让 cur 移动 index 位
                cur = cur.next
                index -= 1
            return cur.val
        else:  # 链表节点不存在,直接返回-1
            return -1

    def add_at_head(self, val: int) -> None:
        cur = self.dummy_head
        old_head = cur.next  # 临时保存原链表的头节点
        cur.next = ListNode(val=val, next=old_head)  # 改变节点指向,让虚拟头节点通过 next 指向新加的节点,新节点则通过 next 指向原链表的头节点
        self.length += 1  # 链表长度+1

    def add_at_tail(self, val: int) -> None:
        cur = self.dummy_head
        while cur.next is not None:  # cur 不是链表最后一个节点
            cur = cur.next
        cur.next = ListNode(val=val, next=None)  # 链表最后一个节点通过 next 指向新加的节点,新节点则通过 next 指向None
        self.length += 1  # 链表长度+1

    def add_at_index(self, index: int, val: int) -> None:
        if 0 <= index <= self.length:
            cur = self.dummy_head
            while index:  # 循环操作,让 cur 移动 index 位
                cur = cur.next
                index -= 1
            if index != self.length:  # 如果 index 不等于链表长度, 那么让cur通过 next 指向新加的节点,新节点则通过 next 指向cur的下个节点
                post_head = cur.next
                cur.next = ListNode(val=val, next=post_head)
            else:  # 如果 index 恰好等于链表长度,那么在链表末尾添加节点
                cur.next = ListNode(val=val, next=None)
            self.length += 1  # 链表长度+1
        elif index < 0:
            self.add_at_head(val)

    def delete_at_index(self, index: int) -> None:
        if 0 <= index < self.length:
            cur = self.dummy_head
            while index:  # 循环操作,让 cur 移动 index 位
                cur = cur.next
                index -= 1
            cur.next = cur.next.next  # 删除节点
            self.length -= 1  # 链表长度-1


def list_node_to_list(node):  # 将单向链表转换为列表
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

测试过程

if __name__ == '__main__':
    obj = MyLinkedList()
    obj.add_at_head(10)  # 在链表开头加新节点
    obj.add_at_tail(3)  # 在链表末尾加新节点
    print(list_node_to_list(obj.dummy_head.next))
    obj.add_at_index(1, 2)  # 在链表索引1位置加新节点
    print(list_node_to_list(obj.dummy_head.next))
    print(obj.get(1))
    obj.delete_at_index(1)  # 删除链表索引1位置的节点
    print(obj.get(1))
    print(list_node_to_list(obj.dummy_head.next))

执行代码后,得到如下结果:

[10, 3]
[10, 2, 3]
2
3
[10, 3]

更多Python编程题,等你来挑战:Python编程题汇总(持续更新中……)

上一篇下一篇

猜你喜欢

热点阅读