Link List Help

[ana_1234]

Hi, I am working on some practice problems for my class and I keep getting stuck on this problem. It is using linked list, I am bit stuck. The problem is to write a function int testloop (listnode *head) that checks to see whether the list 'head' contains a loop.

I just need help on how to approach the problem

#include <iostream>

using namespace std;

class listnode {
 public:
  listnode *next;
};

listnode *l[4];

void create_list();

int testloop(listnode *head);

int main()
{

  int i;

  cout << "creating lists......\n";
  create_list(); // creating lists in *l[4]

  for (i=0; i<4; i++) {
    cout << "testing list " << i << " .....\n";
    if (testloop(l[i]) == 1) 
      cout << "    list " << i << " has a loop.\n";
    else 
      cout << "    list " << i << " does not have a loop.\n\n";
  }
}

[mrnutty]

To test if it contains a loop, i.e is a circular linked list, what you need to do is transverse through the list, and see if head comes up twice. Here is some psuedo-code.

bool isLoopedLinkedList(const listnode* head){
  - bool result = false
  - create a  listnode headCopy
  - while headCopy-> next is not null
        - move headCopy next
        - check if headCopy equals head
            - if so the set result to true and break out of loop
            - else continue
  - endWhile
}

[nezachem]

> if it contains a loop, i.e is a circular linked list

Not exactly. The loop not necessarily includes the head (consider 1->2->3->2). In that case your algorithm will run forever.

The solution takes two pointers traversing the list with different "speeds":

pointer1 <- head
pointer2 <- head
do:
    pointer1 <- next(pointer1)
    pointer2 <- next(next(pointer2))
until 
- either one of the pointers hits the end of list (not a loop)
- or pointer1 becomes equal to pointer2 (loop detected)

[mrnutty]

> if it contains a loop, i.e is a circular linked list

Not exactly. The loop not necessarily includes the head (consider 1->2->3->2). In that case your algorithm will run forever.

The solution takes two pointers traversing the list with different "speeds":

pointer1 <- head
pointer2 <- head
do:
    pointer1 <- next(pointer1)
    pointer2 <- next(next(pointer2))
until 
- either one of the pointers hits the end of list (not a loop)
- or pointer1 becomes equal to pointer2 (loop detected)

Oh I see. I guess I read it wrong. Thanks for the corrections. @OP just make sure you handle the edge cases in this algorithm as well. Ex, if head is null or it only has 1 element.