check for cycles in a linked list in c – dead clever, innit
intro
Oi, you lot! New to C and fancy summat a bit nifty? We’re gonna sling together a lil program to check if a linked list’s got a cycle—ya know, when it loops back on itself like a daft snake eating its tail. It’s dead smart but proper simple—like when I was tryna figure if my mate’s pub crawl route circled back to the same boozer (it did, too smashed to notice). Great for getting your head round pointers in C without a right faff. Let’s have a butcher’s!
code bit
Here’s the code—nowt posh, just a quick job I chucked together. Shoved it in a box so it don’t look like a total shambles on your blog. take a gander:
#include
struct Node { // lil box, innit
int data;
struct Node* next;
};
int hasCycle(struct Node* head) { // sniff out loops
struct Node *slow=head,*fast=head; // two mates
while(fast!=NULL&&fast->next!=NULL) { // fast zips twice as quick
slow=slow->next; // plod along
fast=fast->next->next; // race ahead
if(slow==fast) { // bump into each other?
return 1; // loop found!
}
}
return 0; // no loop
}
int main() { // nearly did void, ha!
struct Node* head=newNode(1); // start the chain
struct Node* second=newNode(2);
struct Node* third=newNode(3);
struct Node* fourth=newNode(4); // few lil nodes
head->next=second;
second->next=third;
third->next=fourth;
fourth->next=NULL; // no loop yet
printf("no cycle check: %d (0’s no loop, 1’s loop)\n",hasCycle(head));
fourth->next=second; // make a loop!
printf("with cycle check: %d (0’s no loop, 1’s loop)\n",hasCycle(head)); // forgot ; once, ugh!
free(head); // tidy up
free(second);
free(third);
free(fourth);
return 0;
}
struct Node* newNode(int data) { // quick node maker
struct Node* node=(struct Node*)malloc(sizeof(struct Node));
node->data=data;
node->next=NULL;
return node;
}
what ya get
Here’s what it chucks out when ya run it. I hard-coded a list, tested no-loop then looped it—worked bang on, mate!
with cycle check: 1 (0’s no loop, 1’s loop)
how it works, kinda
Right, let’s have a natter bout this like we’re slumped at the boozer with a pint—or a bag of pork scratchings, coz I’m Hank Marvin again. I’ll spill it like my tatty old notes from when I was faffing with C. It’s a doddle once ya clock it, swear down!
1. them `#include` bits
This is me nicking my toolkit. `
2. `struct Node` malarky
`struct Node` is my lil box—`int data` for the number, `struct Node* next` for the pointer to the next box. Like chaining mates in a line, innit!
3. `newNode` funtion
`newNode(int data)` whips up a fresh box. `malloc(sizeof(struct Node))` nabs memory, slaps `data` in, sets `next` to `NULL`, and chucks it back. Like adding a new mate to the chain!
4. `int main()` funtion
Gotta have a “main” to kick off—it’s like the door to my local. `int` means I’m lobbing a number out at the end (that `0` says “sorted, guv!”), and them curly `{}` lads keep it all snug. Nearly wrote `void main()`—old me was a right numpty!
5. making the chain: `head` and pals
`head=newNode(1)` starts it—then `second`, `third`, `fourth` with 2, 3, 4. Link `head->next=second`, `second->next=third`, `third->next=fourth`, `fourth->next=NULL` for no loop. Later, `fourth->next=second` makes a cycle—sneaky, eh!
6. `hasCycle` funtion
Here’s the guts! `hasCycle(struct Node* head)` uses two mates: `slow` and `fast`, both at `head`. `while(fast!=NULL&&fast->next!=NULL)` loops—`fast` zips two steps with `fast->next->next`, `slow` plods one with `slow->next`. If `slow==fast`, they’ve bumped, so `return 1`—loop found! Else, `return 0`—no loop. Like a hare and tortoise race!
7. chucking it out: `printf` and `hasCycle`
`printf("no cycle check: %d ...",hasCycle(head))` tests it straight, then after `fourth->next=second`, `printf("with cycle check: %d ...",hasCycle(head))` tests the loop. Forgot a `;` once—CODE JUST DIED, and I was proper fuming!
8. `free` and `return 0` to scarper
`free(head)` and pals tidy up—gotta chuck out the boxes! Then `return 0;` is me legging it, like, “Ta-ta, we’re done!” It’s a C thing—means it all went smooth as a greased weasel.
And that’s yer lot! A cracking lil program to check for cycles in a linked list. Faff with it—chuck in a daft chain, tweak it to say “looped up” if ya fancy. First time I ran this, I forgot the loop and got 0—then added it and bam, 1—dead chuffed, eh! You’re a star already, mate—keep smashing it! 😊
