题目

你需要实现一个链表类 MyLinkedList，支持以下操作： get(index): 获取链表中第 index 个节点的值。如果索引无效，则返回 -1。 addAtHead(value): 在链表头部添加一个值为 value 的节点。 addAtTail(value): 在链表尾部添加一个值为 value 的节点。 addAtIndex(index, value): 在链表的第 index 个节点之前添加值为 value 的节点。如果 index 等于链表长度，则在链表尾部添加节点。如果 index 大于链表长度，则不进行任何操作。 deleteAtIndex(index): 删除链表中第 index 个节点，如果索引无效，则不进行任何操作。

代码实现

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        current = self.head
        for _ in range(index):
            current = current.next
        return current.value

    def addAtHead(self, value: int) -> None:
        new_node = ListNode(value)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def addAtTail(self, value: int) -> None:
        new_node = ListNode(value)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1

    def addAtIndex(self, index: int, value: int) -> None:
        if index < 0 or index > self.size:
            return
        if index == 0:
            self.addAtHead(value)
        else:
            new_node = ListNode(value)
            current = self.head
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            current.next = current.next.next if current.next else None
        self.size -= 1

# 示例用法
if __name__ == "__main__":
    linked_list = MyLinkedList()
    linked_list.addAtHead(1)        # 链表为 1
    linked_list.addAtTail(3)        # 链表为 1 -> 3
    linked_list.addAtIndex(1, 2)    # 链表为 1 -> 2 -> 3
    print(linked_list.get(1))       # 返回 2
    linked_list.deleteAtIndex(1)     # 链表为 1 -> 3
    print(linked_list.get(1))       # 返回 3