loop in a linked list

This is a discussion on loop in a linked list within the C Programming forums, part of the General Programming Boards category; how to find a loop in a linked list and how to remove it after u find? possibly in constant ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    12

    Exclamation loop in a linked list

    how to find a loop in a linked list and how to remove it after u find? possibly in constant space.

    thanx
    krithi

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >how to find a loop in a linked list and how to remove it after u find?
    You mean a cycle where the end of the list links to the beginning? With no knowledge of how the list is set up I would suggest that you have two iterators, one at the first node in the list and one at the third (be sure to check that the list is at least three nodes, this is simple) then move the first iterator by one node and the second by two, checking whether they're equal after each movement. If there's a cycle then at some point both pointers will point to the same address.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    12
    thanx for ur reply how do u remove the loop after u find it

    thanx
    krithi

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >thanx for ur reply how do u remove the loop after u find it
    Just pick the node you want to be the end and set it's next pointer to NULL (or whatever the list uses for a null link).

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with running a double for loop on a linked list
    By Seabass6741 in forum C Programming
    Replies: 4
    Last Post: 03-15-2009, 02:22 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 04:16 PM
  5. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 06:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21