Design Linked List — LeetCode 707 Python Solution
MediumDesignLinked List
- Problem
- #707
- Pattern
- Linked List
- Reading time
- 8 min
- Source
- leetcode.com
The problem
Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
Example
- Input
- ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
- Output
- [null, null, null, null, 2, null, 3]
- Explanation
- MyLinkedList myLinkedList = new MyLinkedList();
Python solution
Python
class MyLinkedList:
def __init__(self):
self.dummy = ListNode()
self.cnt = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.cnt:
return -1
cur = self.dummy.next
for _ in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.cnt, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.cnt:
return
pre = self.dummy
for _ in range(index):
pre = pre.next
pre.next = ListNode(val, pre.next)
self.cnt += 1
def deleteAtIndex(self, index: int) -> None:
if index >= self.cnt:
return
pre = self.dummy
for _ in range(index):
pre = pre.next
t = pre.next
pre.next = t.next
t.next = None
self.cnt -= 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)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 707. Design Linked List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 707. Design Linked List?
- LeetCode 707. Design Linked List is rated Medium on LeetCode.
- What is the time complexity of LeetCode 707. Design Linked List?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 707. Design Linked List?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 707. Design Linked List cover?
- LeetCode 707. Design Linked List is tagged Design and Linked List on LeetCode.