📋

Data Structures

Linked List

~4 mins read

Detect cycle: fast and slow pointers, if the fast finds the end then no cycle

Sort: find the middle with fast and slow pointers then merge

Get intersection: iterate lists with two pointers, if one becomes null then set it to the head of the other list, This assumes there is an intersection. If not it will be an infinite loop so return after a few iterations.

Remove nth from end: use two pointers, one is n steps ahead of the other. When the first pointer reaches the end, the second pointer will be at the nth from the end.

1
2
3
4
5
6
7
8
9
10
11
12
def has_cycle(head):
    if not head:
        return False
    slow, fast = head, head.next
    
    while slow != fast:
        if fast is None or fast.next is None:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True
1
2
3
4
5
6
7
8
9
10
11
12
def find_middle(head):
    if not head:
        return None

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sorted_list_to_bst(head):
    if not head:
        return None

    # Find the middle element of the linked list
    middle = find_middle(head)

    # Create a TreeNode using the middle element
    root = TreeNode(middle.val)

    # If there's only one element in the list, return the root
    if middle == head:
        return root

    # Recursively construct the left and right subtrees
    root.left = sorted_list_to_bst(head)
    root.right = sorted_list_to_bst(middle.next)

    return root
1
2
3
4
5
6
7
8
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    p1, p2 = headA, headB

    while p1 or p2:
        if p1 is p2:
            return p1 
        p1 = headB if not p1 else p1.next
        p2 = headA if not p2 else p2.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
"""

def removeElements(self, head: ListNode, val: int) -> ListNode:
    
    head, head.next = ListNode(0), head
    p = head
    
    while p.next:
        if p.next.val == val:
            p.next = p.next.next
        else:
            p = p.next
            
    return head.next

🔀

🎰