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 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(list_from_array([1, 2, 3, 4, 5])))
# 3 -> 4 -> 5
print(middleNode(list_from_array([1, 2, 3, 4, 5, 6])))
# 4 -> 5 -> 6
2095. Delete the Middle Node of a Linked List¶
from typing import Optional
from leetpattern.utils 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 = list_from_array([1, 2, 3, 4, 5])
print(deleteMiddle(node))
# 1 -> 2 -> 4 -> 5
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 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 = list_from_array([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¶
"""
- Determine if a linked list has a cycle in it.
"""
from typing import Optional
from leetpattern.utils 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(list_from_array([3, 2, 0, -4]))) # False
print(hasCycle(list_from_array([3, 2, 0, -4], 1))) # True
#include <cassert>
#include <iostream>
using namespace std;
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;
}
};
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.hasCycle(head) == true);
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
assert(sol.hasCycle(head2) == false);
ListNode* head3 = new ListNode(1);
assert(sol.hasCycle(head3) == false);
return 0;
}
142. Linked List Cycle II¶
"""
- Given a linked list, return the node where the cycle begins. If there is no cycle, return `None`.
"""
from typing import Optional
from leetpattern.utils 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 = list_from_array([3, 2, 0, -4], 1)
print(detectCycle(head1).val) # 2
head2 = list_from_array([3, 2, 0, -4])
print(detectCycle(head2)) # None
#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;
}