題目

單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個節(jié)點(diǎn)的指針或引用。

請?jiān)O(shè)計(jì)一個單鏈表，并在鏈表類中實(shí)現(xiàn)下列操作：

• get(index)：獲取鏈表中索引 index 節(jié)點(diǎn)的值。如果索引無效，則返回-1。
• add_at_head(val)：在鏈表的第一個節(jié)點(diǎn)之前添加一個值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個節(jié)點(diǎn)。
• add_at_tail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個節(jié)點(diǎn)。
• add_at_index(index,val)：在鏈表中的索引 index 節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長度，則該節(jié)點(diǎn)將追加到鏈表的末尾；如果 index 大于鏈表長度，則不會插入節(jié)點(diǎn)；如果 index 小于0，則在頭部插入節(jié)點(diǎn)。
• delete_at_index(index)：如果索引 index 有效，則刪除鏈表中的索引 index 的節(jié)點(diǎn)。

說明：鏈表節(jié)點(diǎn)的索引 index 是從 0 開始計(jì)算，比如鏈表中索引 1 下的節(jié)點(diǎn)，指的是鏈表中的第二個節(jié)點(diǎn)。

代碼實(shí)現(xiàn)

class ListNode:  # 定義單鏈表
    def __init__(self, val=0, next=None):
        self.val = val  # 鏈表節(jié)點(diǎn)上存儲的元素
        self.next = next  # 指向下一個鏈表節(jié)點(diǎn)


class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode(0)  # 定義虛擬頭節(jié)點(diǎn)
        self.length = 0  # 定義鏈表的長度

    def get(self, index: int) -> int:
        if 0 <= index < self.length:
            cur = self.dummy_head
            cur = cur.next  # 因?yàn)槎嗔艘粋€虛擬頭節(jié)點(diǎn)，所以需提前移動1位
            while index:  # 循環(huán)操作，讓 cur 移動 index 位
                cur = cur.next
                index -= 1
            return cur.val
        else:  # 鏈表節(jié)點(diǎn)不存在，直接返回-1
            return -1

    def add_at_head(self, val: int) -> None:
        cur = self.dummy_head
        old_head = cur.next  # 臨時(shí)保存原鏈表的頭節(jié)點(diǎn)
        cur.next = ListNode(val=val, next=old_head)  # 改變節(jié)點(diǎn)指向，讓虛擬頭節(jié)點(diǎn)通過 next 指向新加的節(jié)點(diǎn)，新節(jié)點(diǎn)則通過 next 指向原鏈表的頭節(jié)點(diǎn)
        self.length += 1  # 鏈表長度+1

    def add_at_tail(self, val: int) -> None:
        cur = self.dummy_head
        while cur.next is not None:  # cur 不是鏈表最后一個節(jié)點(diǎn)
            cur = cur.next
        cur.next = ListNode(val=val, next=None)  # 鏈表最后一個節(jié)點(diǎn)通過 next 指向新加的節(jié)點(diǎn)，新節(jié)點(diǎn)則通過 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:  # 循環(huán)操作，讓 cur 移動 index 位
                cur = cur.next
                index -= 1
            if index != self.length:  # 如果 index 不等于鏈表長度, 那么讓cur通過 next 指向新加的節(jié)點(diǎn)，新節(jié)點(diǎn)則通過 next 指向cur的下個節(jié)點(diǎn)
                post_head = cur.next
                cur.next = ListNode(val=val, next=post_head)
            else:  # 如果 index 恰好等于鏈表長度，那么在鏈表末尾添加節(jié)點(diǎn)
                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:  # 循環(huán)操作，讓 cur 移動 index 位
                cur = cur.next
                index -= 1
            cur.next = cur.next.next  # 刪除節(jié)點(diǎn)
            self.length -= 1  # 鏈表長度-1


def list_node_to_list(node):  # 將單向鏈表轉(zhuǎn)換為列表
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

測試過程

if __name__ == '__main__':
    obj = MyLinkedList()
    obj.add_at_head(10)  # 在鏈表開頭加新節(jié)點(diǎn)
    obj.add_at_tail(3)  # 在鏈表末尾加新節(jié)點(diǎn)
    print(list_node_to_list(obj.dummy_head.next))
    obj.add_at_index(1, 2)  # 在鏈表索引1位置加新節(jié)點(diǎn)
    print(list_node_to_list(obj.dummy_head.next))
    print(obj.get(1))
    obj.delete_at_index(1)  # 刪除鏈表索引1位置的節(jié)點(diǎn)
    print(obj.get(1))
    print(list_node_to_list(obj.dummy_head.next))

執(zhí)行代碼后，得到如下結(jié)果：

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

更多Python編程題，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）