- Swapping Nodes in Pairs
Problem: Given a linked list, swap every two adjacent nodes and return the modified list. You must not modify the values in the nodes, only the nodes themselves.
The key approach involves careful pointer manipulation and the use of a temporray node to preserve references.
We'll use a dummy node to simplify the edge cases. Let's walk through the process step by step:
When implementing, pay attention to:
- The correct placement of temporary nodes
- Only move the primary pointer (cur), not the temporary nodes
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head):
dummy = ListNode(next=head)
current = dummy
while current.next and current.next.next:
# Store references to the nodes we'll be swapping
first_node = current.next
second_node = current.next.next.next
# Perform the swap
current.next = current.next.next
current.next.next = first_node
current.next.next.next = second_node
# Move current to the position before the next pair
current = current.next.next
return dummy.next
## Recursive solution
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head # Base case: empty list or single node
# Nodes to be swapped
first = head
second = head.next
rest = head.next.next # Remaining list after swapping
# Perform the swap
second.next = first
first.next = self.swapPairs(rest) # Recursively swap the rest
return second # New head after swapping
Time complexity: O(n) Space complexity: O(1) for iterative, O(n) for recursive due to call stack
- Removing the Nth Node from the End
Problem: Given a linked list, remove the nth node from the end and return the head of the modified list.
The key insight is to use the two-pointer technique: to remove the nth node from the end, advance the fast pointer n+1 steps first, then move both pointers until the fast pointer reaches the end. This positions the slow pointer at the node before the one to be removed.
Steps:
- Create a dummy node
- Initialize fast and slow pointers at the dummy node
- Move the fast pointer n+1 steps ahead
- Move both pointers until fast reaches the end
- Remove the node after the slow pointer
Based on this approach, here's the implementation:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head, n):
dummy = ListNode(next=head)
slow = dummy
fast = dummy
# Move fast n+1 steps ahead
for _ in range(n + 1):
fast = fast.next
# Move both pointers until fast reaches the end
while fast:
slow = slow.next
fast = fast.next
# Remove the nth node from the end
slow.next = slow.next.next
return dummy.next
Time complexity: O(n) Space complexity: O(1)
Intersection of Two Linked Lists
Problem: Given the heads of two singly linked lists, find and return the node where they intersect. If they don't intersect, return null. The solution must preserve the original structure of both lists.
The key insight is to find the node where the pointers of the two lists are equal (not the values being equal).
Steps:
- Traverse both lists to find their lengths
- Calculate the difference in lengths
- Move the pointer of the longer list ahead by the difference
- Move both pointers until they meet at the intersection point
Here's the implementation:
class Solution:
def getIntersectionNode(self, headA, headB):
# Helper function to get list length
def get_length(node):
length = 0
while node:
length += 1
node = node.next
return length
# Get lengths of both lists
lenA = get_length(headA)
lenB = get_length(headB)
# Set pointers to the start of each list
ptrA = headA
ptrB = headB
# Move the pointer of the longer list ahead by the difference
if lenA > lenB:
for _ in range(lenA - lenB):
ptrA = ptrA.next
else:
for _ in range(lenB - lenA):
ptrB = ptrB.next
# Move both pointers until they meet
while ptrA and ptrB:
if ptrA == ptrB:
return ptrA
ptrA = ptrA.next
ptrB = ptrB.next
return None
Time complexity: O(n + m) Space complexity: O(1)
A more elegant solution without calculating lengths:
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# Handle edge cases
if not headA or not headB:
return None
# Initialize two pointers at the heads of each list
pointerA = headA
pointerB = headB
# Traverse both lists until pointers meet
while pointerA != pointerB:
# Move each pointer forward
# If a pointer reaches the end of its list, redirect to the other list's head
pointerA = pointerA.next if pointerA else headB
pointerB = pointerB.next if pointerB else headA
# When they meet, either at the intersection or both at None
return pointerA
- Linked List Cycle II
Problem: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To detect a cycle, we use the fast and slow pointer technique:
- Start with both pointers at the head
- Move the fast pointer two steps and the slow pointer one step at a time
- If they meet, there is a cycle in the list
The reasoning is that the fast pointer will always enter the cycle first, and they will eventually meet inside the cycle.
Once we've detected a cycle, finding its entrance involves:
When they meet:
- The slow pointer has traveled:
x + y - The fast pointer has traveled:
x + y + n(y + z), where n is the number of full cycles the fast pointer completed before meeting the slow pointer, and (y + z) is the length of the cycle.
Since the fast pointer moves twice as fast as the slow pointer: (x + y) * 2 = x + y + n(y + z)``x = (n - 1)(y + z) + z
When n = 1: x = z
This means that if we place one pointer at the head and another at the meeting point, and move them at the same speed, they will meet at the cycle's entrance.
For n > 1: The same approach works because the pointer starting from the meeting point will complete (n-1) full cycles before meeting the other pointer at the cycle's entrance.
Here's the implementation:
class Solution:
def detectCycle(self, head):
if not head or not head.next:
return None
# Initialize two pointers
slow = head
fast = head
# Find the meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Cycle detected, find the entrance
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
An alternative approach using a set:
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
visited = set()
current = head
while current:
if current in visited:
return current
visited.add(current)
current = current.next
return None
Time complexity: O(n) - The pointers traverse the list at most twice Space complexity: O(1) for the two-pointer approach, O(n) for the set approach