力扣刷题-链表-设计链表

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

# 定义链表
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList(object):

    def __init__(self): # 下方可以直接赋值 里面不用参数也可
        self.dummy_node = ListNode()
        self.size = 0 # 注意定义一个 size


    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size:
            return -1
        current = self.dummy_node.next
        for i in range(index):
            current = current.next
            
        return current.val

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        temp = ListNode()
        temp.val = val
        temp.next = self.dummy_node.next
        self.dummy_node.next = temp
        self.size += 1 # 注意 size+1

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        temp = ListNode()
        temp.val = val
        current = self.dummy_node
        for i in range(self.size):
            current = current.next
        current.next = temp
        # temp.next = None 因为节点定义里面已经有了
        self.size += 1

    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        if index < 0 or index > self.size: # 注意这里没有等于 因为下面是range(index)也不会取到
            return
        temp = ListNode()
        temp.val = val
        current = self.dummy_node
        for i in range(index):
            current = current.next
        temp.next = current.next
        current.next = temp
        self.size += 1 # 注意加1


    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.size:
            return
        current = self.dummy_node
        for i in range(index):
            current = current.next # 先到达位置
        current.next = current.next.next # 再执行删除
        self.size -= 1




# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

难点或者容易出错的地方在于：一些边界的处理 以及 代码健壮性处理 的地方 ：

# 双链表
class ListNode(object):
    def __init__(self, val=0, pred=None, next=None):
        self.val = val
        self.pred = pred
        self.next = next

class MyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def get(self, index):
        if index < 0 or index >= self.size:
            return -1

        if index < self.size // 2: # index在前面一半 就用头节点来遍历 
            current = self.head
            for i in range(index):
                current = current.next
        else:
            current = self.tail
            # x = 0
            # while x < self.size - index - 1:
            #     current = current.pred
            #     x += 1
            for i in range(self.size - index - 1):
                current = current.pred

        return current.val
    
    def addAtHead(self, val):
        temp = ListNode(val=val, next=self.head) # 记得用self
        if self.head:
            self.head.pred = temp
        else: # 需要判断是否存在头节点
            self.tail = temp # 不存在 那么新节点赋给头尾节点
        self.head = temp
        self.size += 1
        
    
    def addAtTail(self, val):
        temp = ListNode(val=val, pred=self.tail)
        if self.tail: # 需要判断尾节点是否存在
            self.tail.next = temp
        else:
            self.tail = temp
        self.head = temp
        self.size += 1
    
    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return
        
        if index == 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        else:
            if index < self.size // 2: # 在前面一半
                current = head
                for i in range(index-1):
                    current = current.next
            else:
                current = self.tail
                x = 0
                while x < self.size - index:
                    current = current.pred
                    x += 1
                temp = ListNode(val=val)
                current.next.pred = temp
                current.next = temp
                self.size += 1

    
    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return
        
        if index == 0:
            self.head = self.head.next # 下一个节点是头节点
            if self.head: # 还需要判断是否存在
                self.head.pred = None
            else:
                self.tail = None # 不存在完全就是空的
        
        elif index == self.size - 1: # !!! 很多细节
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
            else:
                self.head = None
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index):
                    current = current.next
            else:
                current = self.tail
                x = 0
                while x < self.size - index - 1:
                    current = current.pred
                    x += 1
                current.pred.next = current.next
                current.next.pred = current.pred
        
        self.size -= 1 # 记得减1
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

参考：https://programmercarl.com/