LeetCode Day 03 Linked list(1/2)
Published:
Today I’m going to practice Python linked list. LeetCode 203. 707. 206.
Knowledge of linked list
Before we begin, let’s review some of the knowledge points of chained tables.
What is a linked list
Definition: linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
Advantages: the construction of sequential tables need to predict the size of the data to apply for continuous storage space, the expansion of data migration is required, the use of inflexible, Linked lists make full use of computer memory space to achieve flexible memory dynamic management.
Singly linked list
- Definition: A singly linked list is the simplest form of a linked table, each node of which contains two domains - the information domain (element domain) and the link domain. The link points to the next node in the chain table, while the link field of the last node points to a null value.
head stores the first address, elem stores the data, and next points to the next node address.
Doubly linked list
In a ‘doubly linked list’, each node contains, besides the next-node link, a second link field pointing to the ‘previous’ node in the sequence. The two links may be called ‘forward(‘s’) and ‘backwards’, or ‘next’ and ‘prev’(‘previous’).
Question 1
203. Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Idea: There are two types of chained list: empty and non-empty linked list. For non-empty linked list, the operation of the first node is different from the one after it. And add a dummy node in front of the head node, so that the head node can become the same as the following nodes.
# 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 = ListNode(next = head)
cur = dummy
while cur.next!=None:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
Question 2
Design your implementation of the linked list. You can choose to use a singly or doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
current = self.dummy_head.next
for i in range(index):
current = current.next
return current.val
def addAtHead(self, val: int) -> None:
self.dummy_head.next = ListNode(val, self.dummy_head.next)
self.size += 1
def addAtTail(self, val: int) -> None:
current = self.dummy_head
while current.next:
current = current.next
current.next = ListNode(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
current = self.dummy_head
for i in range(index):
current = current.next
current.next = ListNode(val, current.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
current = self.dummy_head
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)
Question 3
Given the
headof a singly linked list, reverse the list, and return the reversed list.
Just change the point of the next pointer in the linked list , and invert it directly , no need to redefine a new linked list .
The two-pointer method can be done
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre