Linked List with Two Pointers
Merge Two Sorted Lists (Leetcode 21)
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-1)
head1 = list1
head2 = list2
dummy1 = dummy
while head1 is not None and head2 is not None:
if head1.val < head2.val:
dummy1.next = head1
head1 = head1.next
else:
dummy1.next = head2
head2 = head2.next
dummy1 = dummy1.next
if head1 is None:
dummy1.next = head2
else:
dummy1.next = head1
return dummy.next
Partition List (Leetcode 86)
We need to ensure the result does not have cycle!!!. Here we set the next of the last node of the second list to None. to avoid the cycle.
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
dummy1 = ListNode(-1)
dummy2 = ListNode(-1)
d1 = dummy1
d2 = dummy2
h = head
while h is not None:
if h.val < x:
d1.next = h
d1 = d1.next
else:
d2.next = h
d2 = d2.next
h = h.next
# NOTE: Here set its next to None to avoid cycle
d2.next = None
d1.next = dummy2.next
return dummy1.next
Merging k Sorted Lists (Leetcode 23)
Key idea: Use a priority queue to store the elements of the k linked list. This gives us a time complexity of O(NlogK).
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(-1)
head = dummy
while heap:
val, i, node = heapq.heappop(heap)
head.next = node
head = head.next
if lists[i].next is not None:
lists[i] = lists[i].next
heapq.heappush(heap, (lists[i].val, i, lists[i]))
return dummy.next
The k-th Element from the End of a Linked List (Leetcode 19)
Key idea: Let one pointer move k steps first, then move both pointers together until the first pointer reaches the end.
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if not head:
return head
p1 = head
p2 = head
while n > 0:
p2 = p2.next
n -= 1
if not p2:
return head.next
while p2 and p2.next:
p1 = p1.next
p2 = p2.next
p1.next = p1.next.next
return head
Middle of the Linked List (Leetcode 876)
Key idea: Use two pointers, one moving one step at a time and the other moving two steps at a time.
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Detect Cycle in a Linked List (Leetcode 141)
Key idea: Use two pointers (Slow and Fast). If there is a cycle, the two pointers will meet at some point.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Intersection of Two Linked Lists (Leetcode 160)
Key idea: Use two pointers to traverse the two linked lists. When one reaches the end, move it to the head of the other linked list. The two pointers will meet at the intersection point.
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p1 = headA
p2 = headB
while p1 != p2:
p1 = p1.next if p1 is not None else headB
p2 = p2.next if p2 is not None else headA
return p1