(*Some may be solved better without them!)
Using 2 pointers :
1.Fast pointer which shifts to the next node by two places.
fast = fast.next.next;
2. Slow pointer which shifts to the next node by one place.
slow = slow.next;
Initially both are initialized to the head pointer.Use of these pointers helps solve linked lists problems in O(n) time and O(1) space.
Example: The problem of determining whether a given linked list is a palindrome.
https://leetcode.com/problems/palindrome-linked-list/The solution that I wrote using this concept takes O(n) time and O(1) space. Though the question as to whether changing the input can be considered as solving the problem in O(1) space has been a topic of discussion. I agree to some of the points in the comments which you can check out below and I do consider it as solving the problem using O(1) space.
My solution to the above problem:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head)
{
ListNode fast_ptr = head;
ListNode slow_ptr = head;
while(fast_ptr!= null && fast_ptr.next != null )
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
if(fast_ptr != null) //odd length of linked list
slow_ptr = slow_ptr.next;
slow_ptr = reverse(slow_ptr);
fast_ptr = head;
while(slow_ptr != null)
{
if(fast_ptr.val != slow_ptr.val)
return false;
fast_ptr = fast_ptr.next;
slow_ptr = slow_ptr.next;
}
return true;
}
public ListNode reverse(ListNode head)
{
ListNode curr = head;
ListNode ptr = head;
ListNode prev = null;
while(curr != null)
{
ptr = curr.next;
curr.next = prev;
prev = curr;
curr = ptr;
}
return prev;
}
}
An important tip while solving problems is to keep checking bits of code. Write a function check if it works and then move to the next bit of the problem. Doing so helps resolve problems on the functional level so it becomes easier to debug the program later.
Other examples of problems that can be solved using slow and fast pointers: