Linked List Cycle

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return false;
        }

        ListNode *slow = head;
        ListNode *fast = head->next;

        while (slow != fast) {
            if (fast == NULL || fast->next == NULL) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x; 
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return true;
}

                                            
public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

var hasCycle = function(head) {
    if (!head || !head.next) {
        return false;
    }
    
    let slow = head;
    let fast = head.next;
    
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    if (head === null) {
        return false;
    }
    
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            return true;
        }
    }
    
    return false;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head
        
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            
            if slow === fast {
                return true
            }
        }
        
        return false
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }
    
    slow, fast := head, head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        
        if slow == fast {
            return true
        }
    }
    
    return false
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(var _x: Int = 0) {
 *   var next: ListNode = null
 * }
 */
object Solution {
  def hasCycle(head: ListNode): Boolean = {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
      slow = slow.next
      fast = fast.next.next
      if (slow == fast) {
        return true
      }
    }
    false
  }
}

To solve this coding challenge, we can utilize the "Floyd’s Cycle-Finding Algorithm" (also known as the Tortoise and Hare algorithm), a classic algorithm that can detect cycles in a linked list with constant space complexity (O(1)). This algorithm employs two pointers, commonly referred to as the slow and fast pointers, which traverse the linked list at different speeds.

Explanation

Initialization :

We first handle the edge cases by checking if the linked list is empty (
head

is
null

) or if it contains only one node (
head.next

is
null

). If either condition is true, the linked list cannot have a cycle, and we return
false

.

Two Pointers Setup :

We initialize two pointers,
slow

and
fast

.
slow

starts at the
head

of the linked list, moving one step at a time (
slow.next

). Meanwhile,
fast

starts at the second node (
head.next

) and moves two steps at a time (
fast.next.next

).

Traverse the List :

As long as
slow

is not equal to
fast

, the loop continues. In each iteration:

Check if
fast

or
fast.next

becomes
null

, which means the end of the list is reached without detecting a cycle. If so, return
false

.
Otherwise, move
slow

pointer one step forward and
fast

pointer two steps forward.

Cycle Detection :

If
slow

equals
fast

, it implies that there is a cycle in the linked list, so we return
true

.

Detailed Steps in Pseudocode

Handle edge cases :

                                            
if head is null or head.next is null:
return false

Initialize two pointers :

                                            
slowPointer = head
fastPointer = head.next

Traverse the list until pointers meet or end of list reaches :

                                            
while slowPointer is not equal to fastPointer:
# Check if fastPointer reaches the end of the list
if fastPointer is null or fastPointer.next is null:
return false

# Move the slow pointer by one step
slowPointer = slowPointer.next

# Move the fast pointer by two steps
fastPointer = fastPointer.next.next

Cycle detected :

                                            
return true

Pseudocode

                                            
# Check initial edge cases
if head is null or head.next is null:
    # If the list is empty or has only one node, it cannot have a cycle
    return false

# Initialize two pointers
slowPointer = head
fastPointer = head.next

# Traverse the linked list
while slowPointer is not equal to fastPointer:
    # if fastPointer reaches the end of the list
    if fastPointer is null or fastPointer.next is null:
        # No cycle found
        return false
    
    # Move slowPointer one step ahead
    slowPointer = slowPointer.next
    
    # Move fastPointer two steps ahead
    fastPointer = fastPointer.next.next

# If we exit the loop, it means slowPointer and fastPointer met
# implying a cycle in the list
return true

The methodology as described ensures that we can efficiently determine if a linked list contains a cycle using O(1) additional space, while the time complexity remains O(n), where n is the number of nodes in the linked list. The use of detailed comments in the pseudocode aids in understanding every step and decision made during the algorithm's execution.