LeetCode每日一题——707. 设计链表

简介: 设计链表的实现。您可以选择使用单链表或双链表。

题目

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能:

get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。

addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。

addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。

addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。

deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

示例

MyLinkedList linkedList = new MyLinkedList();

linkedList.addAtHead(1);

linkedList.addAtTail(3);

linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3

linkedList.get(1); //返回2

linkedList.deleteAtIndex(1); //现在链表是1-> 3 linkedList.get(1); //返回3

提示:

所有val值都在 [1, 1000] 之内。

操作次数将在 [1, 1000] 之内。

请不要使用内置的 LinkedList 库。

思路

直接用列表模拟,列表中每个节点存两个值,一个是当前节点值,一个是下一个节点的值。边界情况有点难确定,打断点打到吐。。。详细思路看下方代码

题解

class MyLinkedList:
    # 初始化一个数组即可
    def __init__(self):
        self.tmp = []
    def get(self, index: int) -> int:
        # index合法即返回,否则-1
        return self.tmp[index][0] if 0<=index<len(self.tmp) else -1
    def addAtHead(self, val: int) -> None:
        # 直接在数组最前方插入该元素
        self.tmp.insert(0, [val,None])
        # 从头开始修改数组中元素的第二个值,也就是该元素的下一个元素值
        for i in range(len(self.tmp)-1):
            # 指向下一个元素
            self.tmp[i][1] = self.tmp[i+1][0]
    def addAtTail(self, val: int) -> None:
        # 直接在结尾添加该元素
        self.tmp.append([val,None])
        # 如果链表中元素>1
        if len(self.tmp) != 1:
            # 需要将倒数第二个元素指向该元素
            self.tmp[-2][1] = val
    def addAtIndex(self, index: int, val: int) -> None:
        # index小于零,在头部插入
        if index < 0:
            index = 0
        # index等于链表长度,在尾部插入
        if index == len(self.tmp):
            self.addAtTail(val)
        # 正常链表内插入
        elif 0<=index<len(self.tmp):
            # 插入到当前位置
            self.tmp.insert(index, [val,None])
            # 修改该位置即之后位置下一个元素的指向
            for i in range(index,len(self.tmp)-1):
                self.tmp[i][1] = self.tmp[i+1][0]
    def deleteAtIndex(self, index: int) -> None:
        # index合法直接删除
        if 0<=index<len(self.tmp):
            self.tmp.pop(index)
            # 若不为空链表
            if len(self.tmp) != 0:
                # 删除的不为链表的最后一个元素,我们需要将删除元素之前的元素的下一个元素指向删除元素的下一个元素
                if index != len(self.tmp):
                    self.tmp[index-1][1] = self.tmp[index][0]
                # 删除的为链表的最后一个元素,我们需要将当前链表的最后一个元素的下一个元素指向None
                else:
                    self.tmp[index-1][1] = None
目录
相关文章
|
15天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
22天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
43 0
Leetcode第21题(合并两个有序链表)
|
22天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
13 0
LeetCode第二十四题(两两交换链表中的节点)
|
22天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
21天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
54 0
|
22天前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
18 0
|
22天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
13 0
|
22天前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0
|
22天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
27 0
|
3月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点