|
| 1 | +# 707.设计链表 |
| 2 | +## 题目 |
| 3 | +``` |
| 4 | +在链表类中实现这些功能： |
| 5 | +get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。 |
| 6 | +addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。 |
| 7 | +addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。 |
| 8 | +addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 |
| 9 | +deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。 |
| 10 | +``` |
| 11 | + |
| 12 | +## 分析 |
| 13 | +* 链表初始化两个属性，一个是链表的大小self.size，一个是虚拟头结点self.head |
| 14 | +* 需要先考虑实现addAtIndex(index,val)方法 |
| 15 | +* addAtHead(val)其实就是addAtIndex(0,val) |
| 16 | +* addAtTail(val)其实就是addAtIndex(self.size,val) |
| 17 | + |
| 18 | +#### 如何实现addAtIndex(index,val) |
| 19 | +* 找到插入位置的前一个节点，如果是头部，那前一个节点就是虚拟头结点 |
| 20 | +* deleteAtIndex(index)和插入一样，都是要找到目标节点的前一个节点 |
| 21 | + |
| 22 | +## 代码 |
| 23 | +```python |
| 24 | + |
| 25 | +class ListNode: |
| 26 | + def __init__(self, x): |
| 27 | + self.val = x |
| 28 | + self.next = None |
| 29 | + |
| 30 | + def __str__(self): |
| 31 | + vals = [str(self.val)] |
| 32 | + next_node = self.next |
| 33 | + while next_node: |
| 34 | + vals.append(str(next_node.val)) |
| 35 | + next_node = next_node.next |
| 36 | + return '->'.join(vals) |
| 37 | + |
| 38 | + |
| 39 | +class MyLinkedList: |
| 40 | + |
| 41 | + def __init__(self): |
| 42 | + self.size = 0 |
| 43 | + self.head = ListNode(0) |
| 44 | + |
| 45 | + def get(self, index: int) -> int: |
| 46 | + # 如果索引无效,返回-1 |
| 47 | + if index < 0 or index >= self.size: |
| 48 | + return -1 |
| 49 | + curr = self.head |
| 50 | + for _ in range(index+1): |
| 51 | + curr = curr.next |
| 52 | + return curr.val |
| 53 | + |
| 54 | + def addAtHead(self, val: int) -> None: |
| 55 | + self.addAtIndex(0, val) |
| 56 | + |
| 57 | + def addAtTail(self, val: int) -> None: |
| 58 | + self.addAtIndex(self.size, val) |
| 59 | + |
| 60 | + def addAtIndex(self, index: int, val: int) -> None: |
| 61 | + # 在链表的第index节点添加值为val的节点 |
| 62 | + # 如果index等于链表长度，添加在尾部 |
| 63 | + # 如果index大于链表长度，不添加 |
| 64 | + # 如果index小于0，添加在首部 |
| 65 | + if index > self.size: |
| 66 | + return |
| 67 | + if index < 0: |
| 68 | + index = 0 |
| 69 | + self.size += 1 |
| 70 | + # 找到要插入位置的前一个节点 |
| 71 | + pred = self.head |
| 72 | + for _ in range(index): |
| 73 | + pred = pred.next |
| 74 | + |
| 75 | + # 要添加的节点 |
| 76 | + to_add = ListNode(val) |
| 77 | + # 插入 |
| 78 | + to_add.next = pred.next |
| 79 | + pred.next = to_add |
| 80 | + |
| 81 | + def deleteAtIndex(self, index: int) -> None: |
| 82 | + # 如果index有效，删除链表中第index个节点 |
| 83 | + if index < 0 or index >= self.size: |
| 84 | + return |
| 85 | + self.size -= 1 |
| 86 | + # 找到要删除的节点的前一个节点 |
| 87 | + pred = self.head |
| 88 | + for _ in range(index): |
| 89 | + pred = pred.next |
| 90 | + |
| 91 | + # 删除 |
| 92 | + pred.next = pred.next.next |
| 93 | + |
| 94 | +``` |
0 commit comments