Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[Code Addition Request]: addition of linked list cycle detection algorithm #897

Closed
3 tasks done
SKG24 opened this issue Oct 28, 2024 · 3 comments
Closed
3 tasks done

[Code Addition Request]: addition of linked list cycle detection algorithm #897

SKG24 opened this issue Oct 28, 2024 · 3 comments
Assignees
@SKG24
Labels
Contributor Denotes issues or PRs submitted by contributors to acknowledge their participation. gssoc-ext hacktoberfest level1 Status: Assigned💻 Indicates an issue has been assigned to a contributor.

Comments

@SKG24
Copy link
Contributor

SKG24 commented Oct 28, 2024 •
edited
Loading

Have you completed your first issue?

  • I have completed my first issue

Guidelines

  • I have read the guidelines
  • I have the link to my latest merged PR

Latest Merged PR Link

#891 (comment)

#891

Project Description

Problem Statement:

Given the head of a linked list, determine if the list contains a cycle. A cycle occurs if a node in the list points back to a previous node, allowing traversal to loop indefinitely.

Solution Approach Using Slow and Fast Pointers:

To detect a cycle, we use two pointers, slow and fast, that traverse the list at different speeds:

  • slow moves one step at a time, while fast moves two steps.
  • If there is a cycle, fast will eventually "lap" slow, causing them to meet.
  • If fast reaches the end of the list (NULL), there is no cycle.

This two-pointer technique efficiently detects cycles in O(n) time complexity without extra space.

Full Name

Sanat Kumar Gupta
@SKG24

Participant Role

gssoc-ext, hacktoberfest
@github-actions GitHub Actions
Copy link

🙌 Thank you for bringing this issue to our attention! We appreciate your input and will investigate it as soon as possible.

Feel free to join our community on Discord to discuss more!

@SKG24
Copy link
Contributor Author

SKG24 commented Oct 28, 2024

please assign this to me!
thank you!

@UTSAVS26 UTSAVS26 added Contributor Denotes issues or PRs submitted by contributors to acknowledge their participation. Status: Assigned💻 Indicates an issue has been assigned to a contributor. level1 labels Oct 28, 2024
SKG24 added a commit to SKG24/PyVerse that referenced this issue Oct 28, 2024
@SKG24
UTSAVS26#897 cycle detection in linked list
6bfe811 
Given the `head` of a linked list, determine if the linked list contains a cycle. A cycle exists if a node in the list points back to an earlier node, creating a loop in the list. Internally, a variable `pos` represents the index of the node that the tail's `next` pointer is connected to. If there is no cycle, `pos` is `-1`.
@SKG24 SKG24 mentioned this issue Oct 28, 2024
Merged
17 tasks
UTSAVS26 added a commit that referenced this issue Oct 29, 2024
@UTSAVS26
Merge pull request #910 from SKG24/main
0cc449c 
#897 cycle detection in linked list
@github-actions GitHub Actions
Copy link

✅ This issue has been closed. Thank you for your contribution! If you have any further questions or issues, feel free to join our community on Discord to discuss more!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@SKG24 SKG24

Labels
Contributor Denotes issues or PRs submitted by contributors to acknowledge their participation. gssoc-ext hacktoberfest level1 Status: Assigned💻 Indicates an issue has been assigned to a contributor.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@UTSAVS26 @SKG24