Linked List
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:
# NOTE: By default, heappush sort the tuple by the first element
# If they tie, it will sort by the second element, and so on
# Custom object will fail, so we need to use i here
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
Reverse Linked List
Reverse Linked List (Leetcode 206)
There are two ways to reverse a linked list, i.e., iteratively and recursively.
The key idea of recursive approach is to firstly traverse to the end of the linked list, then reverse the pointers while backtracking.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
last = self.reverseList(head.next)
head.next.next = head
head.next = None
return last
The key idea of iterative approach is to maintain three pointers, i.e., prev, cur, and nxt. We reverse the pointers iteratively.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
prev, cur, nxt = None, head, head.next
while cur:
cur.next = prev
prev = cur
cur = nxt
if nxt is not None:
nxt = nxt.next
return prev
Palindrome Linked List
Palindrome Linked List (Leetcode 234)
We can use the two-pointer to find the middle of the linked list. Then, we reverse the second half of the linked list and compare it with the first half.
```python