设计链表.md

707.设计链表

题目

在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

分析

• 链表初始化两个属性，一个是链表的大小self.size，一个是虚拟头结点self.head
• 需要先考虑实现addAtIndex(index,val)方法
• addAtHead(val)其实就是addAtIndex(0,val)
• addAtTail(val)其实就是addAtIndex(self.size,val)

如何实现addAtIndex(index,val)

• 找到插入位置的前一个节点，如果是头部，那前一个节点就是虚拟头结点
• deleteAtIndex(index)和插入一样，都是要找到目标节点的前一个节点

代码

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        vals = [str(self.val)]
        next_node = self.next
        while next_node:
            vals.append(str(next_node.val))
            next_node = next_node.next
        return '->'.join(vals)


class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = ListNode(0)

    def get(self, index: int) -> int:
        # 如果索引无效,返回-1
        if index < 0 or index >= self.size:
            return -1
        curr = self.head
        for _ in range(index+1):
            curr = curr.next
        return curr.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        # 在链表的第index节点添加值为val的节点
        # 如果index等于链表长度，添加在尾部
        # 如果index大于链表长度，不添加
        # 如果index小于0，添加在首部
        if index > self.size:
            return
        if index < 0:
            index = 0
        self.size += 1
        # 找到要插入位置的前一个节点
        pred = self.head
        for _ in range(index):
            pred = pred.next

        # 要添加的节点
        to_add = ListNode(val)
        # 插入
        to_add.next = pred.next
        pred.next = to_add

    def deleteAtIndex(self, index: int) -> None:
        # 如果index有效，删除链表中第index个节点
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        # 找到要删除的节点的前一个节点
        pred = self.head
        for _ in range(index):
            pred = pred.next

        # 删除
        pred.next = pred.next.next