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¶
from typing import Optional
from leetpattern.utils import LinkedList, 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
def test_middleNode():
# Test case 1: Odd number of nodes
ll1 = LinkedList([1, 2, 3, 4, 5])
middle1 = middleNode(ll1.head)
result1 = LinkedList(middle1)
assert result1.to_array() == [3, 4, 5]
# Test case 2: Even number of nodes
ll2 = LinkedList([1, 2, 3, 4, 5, 6])
middle2 = middleNode(ll2.head)
result2 = LinkedList(middle2)
assert result2.to_array() == [4, 5, 6]
# Test case 3: Single node
ll3 = LinkedList([1])
middle3 = middleNode(ll3.head)
result3 = LinkedList(middle3)
assert result3.to_array() == [1]
# Test case 4: Two nodes
ll4 = LinkedList([1, 2])
middle4 = middleNode(ll4.head)
result4 = LinkedList(middle4)
assert result4.to_array() == [2]
2095. Delete the Middle Node of a Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
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
def test_deleteMiddle():
ll = LinkedList([1, 3, 4, 7, 1, 2, 6])
ll = LinkedList(deleteMiddle(ll.head))
assert ll.to_array() == [1, 3, 4, 1, 2, 6]
ll = LinkedList([1, 2, 3, 4])
ll = LinkedList(deleteMiddle(ll.head))
assert ll.to_array() == [1, 2, 4]
234. Palindrome Linked List¶
from typing import Optional
from leetpattern.utils 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¶
from typing import Optional
from leetpattern.utils 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¶
from typing import Optional
from leetpattern.utils import LinkedList, 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
def test_reorderList():
ll = LinkedList([1, 2, 3, 4, 5, 6])
assert ll.to_array() == [1, 2, 3, 4, 5, 6]
reorderList(ll.head)
assert ll.to_array() == [1, 6, 2, 5, 3, 4]
ll2 = LinkedList([1, 2, 3, 4, 5])
assert ll2.to_array() == [1, 2, 3, 4, 5]
reorderList(ll2.head)
assert ll2.to_array() == [1, 5, 2, 4, 3]
141. Linked List Cycle¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def has_cycle(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
def test_has_cycle():
ll = LinkedList([3, 2, 0, -4])
ll.make_cycle(pos=1)
assert has_cycle(ll.head)
ll = LinkedList([1, 2])
ll.make_cycle(pos=0)
assert has_cycle(ll.head)
ll = LinkedList([1, 2, 3, 4, 5])
assert not has_cycle(ll.head)
#include <cassert>
#include <iostream>
#include "include/lists.hpp"
using namespace std;
class Solution {
public:
bool has_cycle(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;
}
};
int main() {
Solution solution;
ListNode* head = LinkedList::build({3, 2, 0, -4});
// create cycle
head = LinkedList::make_cycle(head, 1);
assert(solution.has_cycle(head) == true);
// no cycle
ListNode* head2 = LinkedList::build({1, 2});
assert(solution.has_cycle(head2) == false);
// no cycle
ListNode* head3 = LinkedList::build({1});
assert(solution.has_cycle(head3) == false);
return 0;
}
142. Linked List Cycle II¶
from typing import Optional
from leetpattern.utils import LinkedList, 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
def test_detectCycle():
l1 = LinkedList([3, 2, 0, -4])
l1.make_cycle(1)
assert detectCycle(l1.head).val == 2
l2 = LinkedList([3, 2, 0, -4])
assert not detectCycle(l2.head)
#include <cassert>
#include <iostream>
using namespace std;
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;
}
};
int main() {
Solution sol;
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(-4);
head->next->next->next->next = head->next; // Create a cycle
assert(sol.detectCycle(head) == head->next);
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
head2->next->next = head2; // Create a cycle
assert(sol.detectCycle(head2) == head2);
ListNode* head3 = new ListNode(1);
assert(sol.detectCycle(head3) == nullptr);
ListNode* head4 = nullptr;
assert(sol.detectCycle(head4) == nullptr);
return 0;
}