Linked List Fast Slow Pointers

Table of Contents

• 876. Middle of the Linked List (Easy)
• 2095. Delete the Middle Node of a Linked List (Medium)
• 234. Palindrome Linked List (Easy)
• 2130. Maximum Twin Sum of a Linked List (Medium)
• 143. Reorder List (Medium)
• 141. Linked List Cycle (Easy)
• 142. Linked List Cycle II (Medium)
• 457. Circular Array Loop (Medium)
• 2674. Split a Circular Linked List (Medium) 👑

876. Middle of the Linked List

• LeetCode | LeetCode CH (Easy)

• Tags: linked list, two pointers

876. Middle of the Linked List - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
    fast, slow = head, head

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

    return slow


print(middleNode(ListNode.create([1, 2, 3, 4, 5])))
# 3 -> 4 -> 5
print(middleNode(ListNode.create([1, 2, 3, 4, 5, 6])))
# 4 -> 5 -> 6

2095. Delete the Middle Node of a Linked List

• LeetCode | LeetCode CH (Medium)

• Tags: linked list, two pointers

2095. Delete the Middle Node of a Linked List - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
    fast, slow = head, head
    dummy = ListNode(0, head)
    cur = dummy

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

    cur.next = slow.next

    return dummy.next


node = ListNode.create([1, 2, 3, 4, 5])
print(deleteMiddle(node))
# 1 -> 2 -> 4 -> 5

234. Palindrome Linked List

• LeetCode | LeetCode CH (Easy)

• Tags: linked list, two pointers, stack, recursion

234. Palindrome Linked List - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def isPalindrome(head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return True

    def middle(node):
        fast, slow = node, node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse(node):
        cur, pre = node, None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    mid1 = head
    mid2 = reverse(middle(head))

    while mid2:
        if mid1.val != mid2.val:
            return False
        mid1 = mid1.next
        mid2 = mid2.next

    return True


head = ListNode().create([1, 2, 2, 1])
print(isPalindrome(head))  # True

2130. Maximum Twin Sum of a Linked List

• LeetCode | LeetCode CH (Medium)

• Tags: linked list, two pointers, stack

2130. Maximum Twin Sum of a Linked List - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def pairSum(head: Optional[ListNode]) -> int:
    def middle(node):
        fast, slow = node, node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse(node):
        cur, pre = node, None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    list1 = head
    list2 = reverse(middle(head))
    res = float("-inf")

    while list2:
        res = max(res, list1.val + list2.val)
        list1 = list1.next
        list2 = list2.next

    return res


node = ListNode().create([4, 2, 2, 3])
print(pairSum(node))  # 7

143. Reorder List

• LeetCode | LeetCode CH (Medium)

• Tags: linked list, two pointers, stack, recursion

143. Reorder List - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def reorderList(head: Optional[ListNode]) -> None:
    """
    Do not return anything, modify head in-place instead.
    """
    if not head or not head.next:
        return

    # Middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half
    pre, cur = None, slow
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp

    # Merge two linked lists
    first, second = head, pre
    while second.next:
        temp1, temp2 = first.next, second.next
        first.next = second
        second.next = temp1
        first, second = temp1, temp2


head = ListNode.create([1, 2, 3, 4, 5, 6])
print(head)  # 1 -> 2 -> 3 -> 4 -> 5 -> 6
reorderList(head)
print(head)  # 1 -> 6 -> 2 -> 5 -> 3 -> 4

141. Linked List Cycle

• LeetCode | LeetCode CH (Easy)

• Tags: hash table, linked list, two pointers

• Determine if a linked list has a cycle in it.

graph LR
    A((3)) --> B((2))
    B --> C((0))
    C --> D((4))

graph LR
    A((3)) --> B((2))
    B --> C((0))
    C --> D((4))
    D --> B

141. Linked List Cycle - Python Solution

from typing import Optional

from template import ListNode


def hasCycle(head: Optional[ListNode]) -> bool:
    slow, fast = head, head

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

        if slow == fast:
            return True

    return False


print(hasCycle(ListNode.create([3, 2, 0, -4])))  # False
print(hasCycle(ListNode.create([3, 2, 0, -4], 1)))  # True

141. Linked List Cycle - C++ Solution

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
   public:
    bool hasCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (fast == slow) return true;
        }
        return false;
    }
};

142. Linked List Cycle II

• LeetCode | LeetCode CH (Medium)

• Tags: hash table, linked list, two pointers

• Given a linked list, return the node where the cycle begins. If there is no cycle, return None.

graph LR
A[3] --> B[2]
B --> C[0]
C --> D[-4]
D --> B

142. Linked List Cycle II - Python Solution

from typing import Optional

from template import ListNode


def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow, fast = head, head

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

        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None


head1 = ListNode.create([3, 2, 0, -4], 1)
print(detectCycle(head1).val)  # 2
head2 = ListNode.create([3, 2, 0, -4])
print(detectCycle(head2))  # None

142. Linked List Cycle II - C++ Solution

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
   public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (fast == slow) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

457. Circular Array Loop

• LeetCode | LeetCode CH (Medium)

• Tags: array, hash table, two pointers

2674. Split a Circular Linked List

• LeetCode | LeetCode CH (Medium)

• Tags: linked list, two pointers

Comments