Related Topics
Data Structure
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def reverse(self):
prev = None
current = self.head
while current is not None:
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
In the reverse method of the LinkedList class, we start by initializing two pointers: prev and current. prev starts out as None because there is no previous node for the first node in the list. current starts out as the head of the list.
We then enter a loop that continues until we reach the end of the list (current becomes None). In each iteration of the loop, we first save a reference to the next node (next = current.next), so that we don’t lose track of it when we modify current.next.
We then set current.next to point to the previous node (current.next = prev), effectively reversing the link between the two nodes. Finally, we move prev and current forward by one node (prev = current and current = next), so that we can continue iterating through the list.
When we exit the loop, prev will be pointing to the last node in the original list, which is now the head of the reversed list. So we set self.head = prev to update the head of the list to the reversed version.
def has_cycle(head):
if not head:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
In this implementation, head is the head node of the linked list. The function returns True if there is a loop in the linked list and False otherwise.
def find_middle_element(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
In this implementation, head is the head of the linked list. The while loop traverses the linked list with the fast pointer moving at twice the speed of the slow pointer. When the loop terminates, the slow pointer will be pointing to the middle element of the linked list.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: Node, l2: Node) -> Node:
dummy = Node(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
if l1:
curr.next = l1
elif l2:
curr.next = l2
return dummy.next
In the above code, we define a Node class to create a linked list. The mergeTwoLists function takes two linked lists as input and returns the merged list. We create a dummy node as the head of the merged list, and a current pointer to keep track of the current node being processed. We then traverse the two linked lists, and compare the values of the nodes at the pointers. The smaller value node is added to the merged list, and the corresponding pointer is moved to the next node. Once either one of the lists is fully traversed, we add the remaining nodes in the non-traversed list to the merged list. Finally, we return the merged list.
def delete_node(node):
# check if the given node is not the last node in the linked list
if node.next is not None:
# copy the data from the next node to the node to be deleted
node.data = node.next.data
# point the next pointer of the node to be deleted to the node next to the next node
node.next = node.next.next
# delete the next node
del node.next
else:
raise ValueError("Cannot delete last node using this method")
In the above code, node is the node to be deleted, and it is assumed that the linked list is singly linked.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.top is None:
return None
data = self.top.data
self.top = self.top.next
return data
def peek(self):
if self.top is None:
return None
return self.top.data
def isEmpty(self):
return self.top is None
Note that this implementation has a time complexity of O(1) for all operations.
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.