It is already given that the loop is formed at the second node of the linked list, i.e. the second node has two incoming links, one from the first and the other from the last node. The address of the last node that links to the second node and forms the loop needs to be found.

/* Solution to a problem asked at:
   http://www.orkut.co.in/Main#CommMsgs?cmm=1027&tid=5470285126748556338

Author: Susam Pal */

#include <stdio.h> #include <stdlib.h>

struct node { int data; struct node *next; };

/* Detects the loop and returns the address to the last node that links to the second node, i.e. head->next. Consumes O(1) memory and O(n) time. */ struct node *last_node(struct node *head) { struct node *p1; struct node *p2;

p1 = p2 = head->next; while (p1->next != p2->next->next) { p1 = p1->next; p2 = p2->next->next; } return p1; }

struct node *create_node(int data) { struct node *p; p = (struct node *) malloc(sizeof *p); p->data = data; return p; }

int main() { struct node *p; struct node *head; struct node *second; struct node *second_node;

p = head = create_node(1); p = p->next = create_node(2); p = p->next = create_node(3); p = p->next = create_node(4); p = p->next = create_node(5); p = p->next = create_node(6); p = p->next = create_node(7); p->next = head->next; /* Loop to second node */

p = last_node(head); printf("Last node has address %p and data %d.\n", p, p->data); return 0; }

Output from my system:
Last node has address 0x7330d0 and data 7.

No comments

Post a comment

RSS