Question: An implementation of a singly double list
Explanation: Here we have 6 different methods on the class of the linked list. Where you can get, addAthead, addAtTail, addAtindex and deleteAtIndex. Each of these methods perform an action related to the singly linkedList behaviour.
class MyLinkedList:
def __init__(self):
"""
Initialize your data structure here.
"""
self.list= []
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
if index >= len(self.list):
return -1
return self.list[index]
def addAtHead(self, val: int) -> None:
"""
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
"""
self.list= [val] + self.list
def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""
self.list.append(val)
def addAtIndex(self, index: int, val: int) -> None:
"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
"""
if index > len(self.list):
return
self.list.insert(index, val)
def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
if index >= len(self.list):
return
del self.list[index]
# 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: Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Explanation: we check if a linked list has a cycle in by creating 2 pointers. A fast runner and a slow runner. When they both meet each other, that means the linkedList is cyclic.
class Solution:
def hasCycle(self, head) -> bool:
fast, slow = head, head
while fast and fast.next:
slow= slow.next
fast= fast.next.next
if fast == slow:
return True
return False
Question:Linked List Cycle II: Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Explanation: Similiar to the previous question, we try to find out at which node does the cycle start. For this, we used Floyd’s cycle detection method. Where when the fast and slow runner meets, the fast runner is reset to the head, and when it meets the slow runner again, that is the start of the cycle.
# use Floyd's cycle detection
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while fast and fast.next:
slow= slow.next
fast= fast.next.next
# where they meet, take the fast back to head
# the distance between head and the start of the cycle
# equals the distance between where they met and the start of the cycle
if fast == slow:
fast= head
while fast != slow:
fast= fast.next
slow= slow.next
return slow
return None
Question:Intersection of Two Linked Lists: Write a program to find the node at which the intersection of two singly linked lists begins. Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Explanation: While both linked linkedList do not equal each other, We iterate through the length of one linkedList, and then jump to the other. If they are linked, both linkedList will eventually cross.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
#return None directly if headA or headB are null
if not headA or not headB:
return None
#keep the original structure of headA and headB by saving them
savedA, savedB = headA, headB
# while both values are not equal iterate. When none is reached
# to one of the lists, go to the other list and iterate from there.
# if there is a connection they will both meet at the same node
while headA != headB:
headA= savedB if not headA else headA.next
headB= savedA if not headB else headB.next
return headA
Question:Remove Nth Node From End of List: Given a linked list, remove the n-th node from the end of list and return its head.
Explanation: In linkedList, deleting works by skipping the reference connection. Such as
``` second.next = second.next.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
We move the first pointer to where we want to delete the node, and then traverse the second node, the same number of steps as the first node when it reaches None/null. This is the node to be deleted and we can skip is using the line shown earlier.
```Python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
first, second = head, head
#Take the first.next to the position of the node
for i in range(n):
first= first.next
# if first.next is None, then nothing to delete and return the head as is
if not first:
return head.next
# iterate both till null is reached
while first.next:
first= first.next
second= second.next
# This connects the second.next to second.next.next, by dropping the node
second.next = second.next.next
return head
Question:Reverse a singly linked list.
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
A linked list can be reversed either iteratively or recursively. Could you implement both?
Explanation: The first thing we do is create a temprorily variable to store the pointer of the next value using next= head.next, we later point this next to the head head= next. We then point the the head.next to the previous value head.next= prev so we can reverse the arrows. We then point the prev to the current head.
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev= None
# we flip the orientation of the arrow to reverse the list
while head:
next= head.next # temp variable to keep track of what is suppose to be next
head.next= prev # We point the head.next to the prev value
prev= head # We update the prev value to be the current head
head= next # We update the head to point next, which was the temp value we created
reversed = prev
return reversed
Question: Remove Linked List Elements
Explanation:
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(None)
dummy.next = head
prev = dummy
curr = head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return dummy.next
Question: Odd Even Linked List
Explanation:
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
even_head= ListNode(None)
even= even_head
odd_head= ListNode(None)
odd= odd_head
while head:
odd.next= head
odd= odd.next
even.next= head.next
even= even.next
head= head.next.next if even else None
odd.next= even_head.next
return odd_head.next
Question: Palindrome Linked List
Explanation:
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
fast= head
slow= head
rev= None
tmp_slow= None
while fast and fast.next:
fast= fast.next.next
tmp_slow= slow.next
slow.next= rev
rev= slow
slow= tmp_slow
if fast:
slow= slow.next
while slow:
if slow.val != rev.val:
return False
slow= slow.next
rev= rev.next
return True
Question: Explanation:
Question: Explanation: