Given: A singly linked list.
Goal: Return the middle node of the linked list.class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def middleNode(head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next # move 1 step
fast = fast.next.next # move 2 steps
return slowDelete Node in a Linked List Delete
You are given only a reference to a node (not the head) in a singly linked list. The node is not the tail.
You need to delete this node from the list.
You cannot traverse from the head to find the previous node.
You do not have access to the previous node, so you can't modify its next pointer.
You copy the value of the next node into the current node, and then delete the next node instead.
class Node:
def deleteNode(node: ListNode) -> None:
node.val = node.next.val # Step 1: Copy value from next node
node.next = node.next.next # Step 2: Skip the next nodeA dummy node is a placeholder node used as the starting point of a new linked list.
It often has a value like -1 or 0, and its main purpose is not for storing data but to help simplify code logic.
To avoid handling special cases when dealing with the head of the list.
To build a new list easily without checking if it’s the first node.
To simplify pointer manipulation (especially useful in deletion or partitioning problems).
Prevents null pointer exceptions during iteration or insertion.
You don’t know which node will be the head of the merged list, so using a dummy node allows you to build the merged list without worrying about head initialization.
function insertAtHead(head, value):
newNode = Node(value)
newNode.next = head
return newNode // new head
class Node:
def __init__(self, val):
self.val = val
self.next = None
def insertAtHead(head, value):
newNode = Node(value)
newNode.next = head
return newNode
function insertAtTail(head, value):
newNode = Node(value)
if head is null:
return newNode
temp = head
while temp.next != null:
temp = temp.next
temp.next = newNode
return head
def insertAtTail(head, value):
newNode = Node(value)
if not head:
return newNode
temp = head
while temp.next:
temp = temp.next
temp.next = newNode
return head
function deleteFromHead(head):
if head is null:
return null
return head.next
def deleteFromHead(head):
if not head:
return None
return head.next
function deleteFromTail(head):
if head is null or head.next is null:
return null
temp = head
while temp.next.next != null:
temp = temp.next
temp.next = null
return head
def deleteFromTail(head):
if not head or not head.next:
return None
temp = head
while temp.next.next:
temp = temp.next
temp.next = None
return head
function search(head, target):
temp = head
while temp != null:
if temp.val == target:
return true
temp = temp.next
return false
def search(head, target):
temp = head
while temp:
if temp.val == target:
return True
temp = temp.next
return False
function reverseList(head):
prev = null
curr = head
while curr != null:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev // new head
def reverseList(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
function getLength(head):
count = 0
temp = head
while temp != null:
count += 1
temp = temp.next
return count
def getLength(head):
count = 0
temp = head
while temp:
count += 1
temp = temp.next
return count
function printList(head):
temp = head
while temp != null:
print temp.val
temp = temp.next
def printList(head):
temp = head
while temp:
print(temp.val, end=" -> ")
temp = temp.next
print("None")
In the 3Sum problem, you're looking for unique triplets that sum to zero. So, once you find a triplet, you need to skip over duplicate values from both the left pointer (l) and the right pointer (r) to avoid considering the same triplet more than once.
def threeSum(nums):
nums.sort() # Sort the array
n = len(nums)
res = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]: # Skip duplicates for 'i'
continue
l, r = i + 1, n - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total < 0:
l += 1
elif total > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
# Skip duplicates for 'l' and 'r'
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return res
Skip duplicates for i:
i pointer forward, check if nums[i] is equal to nums[i - 1]. This avoids considering the same starting element multiple times.Skip duplicates for l:
while l < r and nums[l] == nums[l + 1] to skip over duplicates on the left side (to avoid reusing the same value for l).Skip duplicates for r:
while l < r and nums[r] == nums[r - 1] to skip duplicates on the right side.The check while l < r and nums[l] == nums[l+1] is valid after finding a valid triplet and moving l or r. It's there to ensure that you don't pick the same number twice for l and r.
Without it, you might end up including the same triplet multiple times (e.g., if nums[l] == nums[l+1], the triplet formed with both values would be identical).
For an input like:
nums = [-1, 0, 1, 2, -1, -4]
[-4, -1, -1, 0, 1, 2]i = -4 and try to find pairs that sum to 4 (to make a total of 0).[-1, 0, 1]), you'd use the deduplication logic to skip duplicate values of l and r, ensuring that each triplet is unique.Yes, while l < r and nums[l] == nums[l+1] can be used in 3Sum, but only after finding a valid triplet and ensuring no duplicate triplets are added to the result. The right logic here is to carefully avoid revisiting the same values when adjusting the l and r pointers.
Let me know if you'd like a detailed step-by-step example of how the function works for a specific input!
Use two pointers to remove the Nth node from the end of the linked list in one pass.
First pass: Count the total number of nodes in the list (length).
Second pass: Traverse again and stop at the (length - n)th node (just before the one to be deleted).
Update the next pointer to skip the target node.