MediumNo. 0707

Design Linked List — LeetCode 707 Python Solution

Topics
Design, Linked List
Reading time
8 min

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

PythonSolution
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

Time
O(n)
Space · auxiliary
O(1)

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

Related problems
No.ProblemDifficulty
1206Design SkiplistHard
0019Remove Nth Node From End of ListMedium
0021Merge Two Sorted ListsEasy
0024Swap Nodes in PairsMedium
0025Reverse Nodes in k-GroupHard
0061Rotate ListMedium

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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.