Solution to LeetCode 203 Remove Linked List Elements and 707 Design Linked List.
LeetCode 203
Remove Linked List Elements (Easy) [link]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
cur = dummy_head
while cur.next != None:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_head.next
LeetCode 707
Design Linked List (Medium). [link]
Note that size is always equal to the max index in the linked list.
Time complexity of addAtHead: O(1), addAtTail: O(1), addAtIndex: O(n), deleteAtIndex:O(n), get: O(n).
class ListNode:
def __init__(self,x):
self.val = x
self.next = None
class MyLinkedList(object):
def __init__(self):
self.size = 0
self.head = ListNode(0) # pseudo head
def get(self, index):
"""
:type index: int
:rtype: int
"""
if index < 0 or index >= self.size:
return -1
cur = self.head
for _ in range(index + 1):
cur = cur.next
return cur.val
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(0, val)
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(self.size, val)
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
if index > self.size:
return
if index < 0:
index = 0
self.size += 1 # update the size
pred = self.head
for _ in range(index): # find the node
pred = pred.next
newNode = ListNode(val) # creat a new node
newNode.next = pred.next # add the new node
pred.next = newNode
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
if index < 0 or index >= self.size:
return
self.size -= 1 # update the size
pred = self.head
for _ in range(index): # find the node
pred = pred.next
pred.next = pred.next.next # delete the node
# 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)
