Leetcode 707. 设计链表

1.题目基本信息

1.1.题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

1.2.题目地址

https://leetcode.cn/problems/design-linked-list/description/

2.解题方法

2.1.解题思路

双链表

2.2.解题步骤

第一步，定义节点，双链表节点结构有val、next、prev属性。

第二步，初始化链表，定义头部哑结点和尾部哑结点，并将两节点进行连接。

第三步，遍历链表index次，从head节点开始，可以获取index下标的节点，如果获取的节点为尾部哑结点，直接退出返回-1，因为超出范围了。

第四步，设计在头尾加节点，有dumbHead、dumbTail俩哑结点，这俩功能很容易就能实现。

第五步，从head开始遍历index次获取下标为index的节点，并在该节点的前面添加上新节点，如果获取到的节点为None，说明index超出范围了，不能添加，返回-1。

第六步，也是从head开始遍历index次获取需要删除的节点，然后删除，需要注意的是如果获取到的需要删除的节点是尾部哑结点，则不删除，因为此时索引超出范围了。

3.解题代码

Python代码

class LinkNode():
    def __init__(self,val,next=None,prev=None):
        self.val=val
        self.next=next
        self.prev=prev

# 双链表结构；第一步，定义节点，双链表节点结构有val、next、prev属性。第二步，初始化链表，定义头部哑结点和尾部哑结点，并将两节点进行连接。第三步，遍历链表index次，从head节点开始，可以获取index下标的节点，如果获取的节点为尾部哑结点，直接退出返回-1，因为超出范围了。第四步，设计在头尾加节点，有dumbHead、dumbTail俩哑结点，这俩功能很容易就能实现。第五步，从head开始遍历index次获取下标为index的节点，并在该节点的前面添加上新节点，如果获取到的节点为None，说明index超出范围了，不能添加，返回-1。第六步，也是从head开始遍历index次获取需要删除的节点，然后删除，需要注意的是如果获取到的需要删除的节点是尾部哑结点，则不删除，因为此时索引超出范围了。
class MyLinkedList:
    def __init__(self):
        self.headDumbNode=LinkNode(None)
        self.tailDumbNode=LinkNode(None)
        self.headDumbNode.next=self.tailDumbNode
        self.tailDumbNode.prev=self.headDumbNode

    def get(self, index: int) -> int:
        node=self.headDumbNode.next
        for i in range(index):
            if node is self.tailDumbNode:
                return -1
            node=node.next
        result=node.val
        return result if result is not None else -1

    def addAtHead(self, val: int) -> None:
        node=LinkNode(val)
        node.next=self.headDumbNode.next
        node.next.prev=node
        self.headDumbNode.next=node
        node.prev=self.headDumbNode

    def addAtTail(self, val: int) -> None:
        node=LinkNode(val)
        node.prev=self.tailDumbNode.prev
        node.prev.next=node
        node.next=self.tailDumbNode
        self.tailDumbNode.prev=node

    def addAtIndex(self, index: int, val: int) -> None:
        node=self.headDumbNode.next
        for i in range(index):
            node=node.next
            if node is None:
                return
        newNode=LinkNode(val)
        newNode.prev=node.prev
        newNode.prev.next=newNode
        newNode.next=node
        node.prev=newNode

    def deleteAtIndex(self, index: int) -> None:
        node=self.headDumbNode.next
        for i in range(index):
            if node is self.tailDumbNode:
                return
            node=node.next
        if node is not self.tailDumbNode:
            node.next.prev=node.prev
            node.prev.next=node.next