[Go] Linked List - Linked List Cycle

 

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

 

My code

func hasCycle(head *ListNode) bool {
	if head == nil {
		return false
	}
	slow, fast := head, head.Next
	for slow != nil && fast != nil && fast.Next != nil && slow != fast {
		slow = slow.Next
		fast = fast.Next.Next
	}

	return slow == fast
}

• if head is nil, code doesn't need to be run, so it will return false.
• slow and fast will have head and head.next. 
• when slow, fast and fast.Next must not be nil and slow and fast is not same with fast, for loop will run.
• after that, return will check slow and fast is same.

sample 0 ms submission

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
	var fast, slow *ListNode
	fast = head.Next
	slow = head
	for fast != nil && fast.Next != nil {
		if fast == slow {
			return true
		}
		fast = fast.Next.Next
		slow = slow.Next
	}
    return false
}

• when head or head.Next is nil, false will be returned.
• fast and slow will be delared to *ListNode and will take head.Next and head address.
• when fast and fast.Next is not nil, for loop will run.
• if condition will return when fast and slow is same.
• if not, fast will take Next.Next, and slow will take Next.

sample 2 ms submission

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    
    slow, fast := head, head.Next
    
    for slow != fast {
        if slow.Next != nil && fast.Next != nil && fast.Next.Next != nil {
            slow = slow.Next
            fast = fast.Next.Next
        } else {
            return false
        }
    }
    
    return true
}

sample 3 ms submission

func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

sample 4 ms submission

func hasCycle(head *ListNode) bool {
    //change values to mark them as seen as you go
    // use a hashmap/ keep track of how many things point to each node
    // trying to think of an o(1) space without changing the values but thats probably not possible
    if (head == nil) {
        return false;
    } else if (head.Val == 1000000) {
        return true;
    } else {
        head.Val = 1000000;
        return hasCycle(head.Next);
    }
}

sample 5 ms submission

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    
    hare := head.Next.Next
    tortoise := head.Next
    
    for hare != tortoise {
        if hare == nil || tortoise.Next == nil || hare.Next == nil {
            return false
        }
        hare = hare.Next.Next
        tortoise = tortoise.Next
    }
    
    return true
}

sample 6 ms submission

func hasCycle(head *ListNode) bool {
    
    if head == nil || head.Next == nil {
        return false
    }
    
    tracker := head.Next
    
    for tracker != nil && tracker.Next != nil {
        if head == tracker {
            return true
        }
        
        head = head.Next
        tracker = tracker.Next.Next
    }
    
    return false
}

sample 4300 KB submission

func hasCycle(head *ListNode) bool {
   if head == nil {
		return false
	}

	fast := head.Next
	slow := head

	for fast != nil && fast.Next != nil {
		if fast == slow {
			return true
		}

		fast = fast.Next.Next
		slow = slow.Next
	}
	return false
}

sample 4400 KB submission

func hasCycle(head *ListNode) bool {
    slowP := head
    fastP := head
    for slowP != nil && fastP != nil && fastP.Next != nil {
        slowP = slowP.Next
        fastP = fastP.Next.Next
        if slowP == fastP {
            return true
        }
    }
    return false
}

// func hasCycle(head *ListNode) bool {
//     slowP := head
//     if head == nil {
//         return false
//     }
//     fastP := head.Next
//     for {
//         if slowP == nil || fastP == nil {
//             return false
//         }
//         if slowP == fastP {
//             return true
//         }
//         slowP = slowP.Next
//         fastP = fastP.Next.Next
//     }
//     return false
// }

// func hasCycle(head *ListNode) bool {
//     nodeMap := make(map[*ListNode]*ListNode, 0)
//     for {
//         if head == nil {
//             return false
//         }
//         if _, ok := nodeMap[head]; ok {
//             return true
//         }
//         nodeMap[head] = head
//         head = head.Next
//     }
// }

// import "fmt"

// func main() {
// 	fmt.Println("Hello, 世界")
// 	qq := ListNode{Val: 3, Next: nil}
// 	pp := ListNode{Val: 2, Next: &qq}
// 	ll := ListNode{Val: 1, Next: &pp}
// 	qq.Next = &ll
// 	fmt.Print(hasCycle(&ll))
// }