Set as Homepage   Add to Favourites   Recommend   Contact



Menu

∙ Home
∙ Index (All Topics)
∙ About Me
∙ About This Blog
∙ Favourite Links
∙ RSS Feed

Categories

∙ ASP & PHP (1)
∙ HTML, XML and CSS (2)
∙ C / C++ (5)
∙ Java, JSP and Servlet (0)
∙ SQL-Oracle-PL/SQL (28)
∙ Operating Systems (1)
∙ OFF-Topic (8)

Popular Topics (Top 10)

∙ Decode Function in Oracle SQL (70916)

∙ Derin anlamlı sözler - Bunlar da Türkçe olanlar :) (67509)

∙ Oracle performance analysis - Tracing and performance evaluation (52623)

∙ When a transaction begins? (44907)

∙ Differences between C and C++ (44061)

∙ Turkcell Staj Günlüğü - 1: Introduction to Oracle (39878)

∙ Implicit vs. Explicit cursors - Performance analysis (23496)

∙ Turkcell Staj Günlüğü - 9: "SQL, PL/SQL and Java" ve "Redo Internals" (21500)

∙ Turkcell Staj Günlüğü - 4: Transaction Management (20459)

∙ Finding and Removing Loop on a Singly-Linked List (20377)


Most Recent (Last 10)

∙ Matematik Asla Yalan Söylemez!

∙ Finding and Removing Loop on a Singly-Linked List

∙ Obfuscated C

∙ Is C a Vitamin? Yes, of course...

∙ Differences between C and C++

∙ Whence C? Why C? Whither C?

∙ Türkçe Karakterli Domain'lerin İç Yüzü

∙ Windows Source Codes

∙ Decode Function in Oracle SQL

∙ Hello World!


Recent Comments (Last 10)

∙ "tebrikler" By yasin on Turkcell Staj Günlüğü - 5: Startup, Shutdown

∙ "Gercekten Güzel Bir Çalışma" By Hüseyin Karabakla on Neden hazır blog'ları kullanmadım ki?

∙ "Konu paralelinde güzel bir özet ek okuma - " By TongucY on Oracle performance analysis - Tracing and performance evaluation

∙ "harika" By burak ozcan on Derin anlamlı sözler - Bunlar da Türkçe olanlar :)

∙ "Tebrikler" By Tarık Bayzın on Turkcell Staj Günlüğü - 1: Introduction to Oracle

∙ "Gayet Başarılı.." By Fahri ATES on Turkcell Staj Günlüğü - 1: Introduction to Oracle

∙ "Helal olsun" By ender onder on Turkcell Staj Günlüğü - 5: Startup, Shutdown

∙ "tebrikler.." By ender ondeer on Turkcell Staj Günlüğü - 4: Transaction Management

∙ "Adulation?" By fizikci on Matematik Asla Yalan Söylemez!

∙ "Rehberlik için çook teşekkürler" By Pınar Tanrıverdi on Kahin'e yolculuk nasıl başlamalı?


Archive (Last 12 Months)

∙ Feb, 2008 (4)
∙ Jan, 2008 (2)
∙ Dec, 2007 (1)
∙ Sep, 2007 (4)
∙ Aug, 2007 (9)
∙ Jul, 2007 (22)
∙ Jun, 2007 (3)
∙ Index (All Records)

Other Related Blogs

∙ Tom Kyte’s Blog
∙ Steven Feuerstein’s Blog
∙ Jonathan Lewis’s Blog
∙ H.Tonguç Yılmaz Oracle Blog
∙ Mennan Tekbir's Blog
∙ Hakkı Oktay’s Blog
∙ Osman Çam’s Blog

Stats

Total Topics
Total Topic Views
Total Comments
Unique Visitors
Total Visitors
: 45
: 886409
: 44

About this blog…
About this blog…
About Me
About Me
Favourite Links
Favourite Links
Neden hazır blog'ları kullanmadım ki?
Neden hazır blog'ları kullanmadım ki?
CSS is more powerful than you imagine
CSS is more powerful than you imagine
Turkcell Staj Günlüğü - 1: Introduction to Oracle
Turkcell Staj Günlüğü - 1: Introduction to Oracle
Turkcell Staj Günlüğü - 2: Data Blocks, Extends and Segments
Turkcell Staj Günlüğü - 2: Data Blocks, Extends and Segments
Kahin'e yolculuk nasıl başlamalı?
Kahin'e yolculuk nasıl başlamalı?
Turkcell Staj Günlüğü - 3: Tablespaces, Datafiles and Control Files
Turkcell Staj Günlüğü - 3: Tablespaces, Datafiles and Control Files
Turkcell Staj Günlüğü - 4: Transaction Management
Turkcell Staj Günlüğü - 4: Transaction Management
Image formats - Which to use when
Image formats - Which to use when
Turkcell Staj Günlüğü - 5: Startup, Shutdown
Turkcell Staj Günlüğü - 5: Startup, Shutdown
Turkcell Staj Günlüğü - 6: Oracle Architecture
Turkcell Staj Günlüğü - 6: Oracle Architecture
ASP - Locales and Codepages
ASP - Locales and Codepages
Oracle performance analysis - Tracing and performance evaluation
Oracle performance analysis - Tracing and performance evaluation
Oracle performance analysis - Autotrace workshop
Oracle performance analysis - Autotrace workshop
Oracle performance analysis - Runstats workshop
Oracle performance analysis - Runstats workshop
Oracle performance analysis - Tkprof workshop
Oracle performance analysis - Tkprof workshop
Some favourite quotes
Some favourite quotes
Derin anlamlı sözler - Bunlar da Türkçe olanlar :)
Derin anlamlı sözler - Bunlar da Türkçe olanlar :)
Turkcell Staj Günlüğü - 7: Concurrency and Consistency
Turkcell Staj Günlüğü - 7: Concurrency and Consistency
"Kurtuluş"un hikayesi
"Kurtuluş"un hikayesi
Turkcell Staj Günlüğü - 8: Statement Processing and CBO
Turkcell Staj Günlüğü - 8: Statement Processing and CBO
When a transaction begins?
When a transaction begins?
Implicit vs. Explicit cursors - Performance analysis
Implicit vs. Explicit cursors - Performance analysis
Turkcell Staj Günlüğü - 9: "SQL, PL/SQL and Java" ve "Redo Internals"
Turkcell Staj Günlüğü - 9: "SQL, PL/SQL and Java" ve "Redo Internals"
Affect of gathering table stats to decision of CBO
Affect of gathering table stats to decision of CBO
Bind is bad :) - An interesting case of bind variables fails
Bind is bad :) - An interesting case of bind variables fails
When the explanation doesn't sound quite right...
When the explanation doesn't sound quite right...
Turkcell Staj Günlüğü - 10: Import, Export ve SQL Loader
Turkcell Staj Günlüğü - 10: Import, Export ve SQL Loader
Turkcell Staj Günlüğü - 11: Autonomous Transactions ve Dynamic SQL
Turkcell Staj Günlüğü - 11: Autonomous Transactions ve Dynamic SQL
Difference between db block gets and consistent gets
Difference between db block gets and consistent gets
Object-Oriented Features of Oracle - Part 1: Native Datatypes vs. Object Datatypes
Object-Oriented Features of Oracle - Part 1: Native Datatypes vs. Object Datatypes
Object-Oriented Features of Oracle - Part 2: Object Types and Collection types
Object-Oriented Features of Oracle - Part 2: Object Types and Collection types
Object-Oriented Features of Oracle - Part 3: Object Tables, Object Views and REFs
Object-Oriented Features of Oracle - Part 3: Object Tables, Object Views and REFs
Examining show_space
Examining show_space
Turkcell Staj Günlüğü - 12: Partitioning
Turkcell Staj Günlüğü - 12: Partitioning
Hello World!
Hello World!
Decode Demo #1
Decode Demo #1
Decode Demo #2
Decode Demo #2
Decode Demo #3
Decode Demo #3
Decode Demo #4
Decode Demo #4
Decode Function in Oracle SQL
Decode Function in Oracle SQL
Windows Source Codes
Windows Source Codes
Türkçe Karakterli Domain'lerin İç Yüzü
Türkçe Karakterli Domain'lerin İç Yüzü
Whence C? Why C? Whither C?
Whence C? Why C? Whither C?
Differences between C and C++
Differences between C and C++
Is C a Vitamin? Yes, of course...
Is C a Vitamin? Yes, of course...
Obfuscated C
Obfuscated C
Finding and Removing Loop on a Singly-Linked List
Finding and Removing Loop on a Singly-Linked List
Matematik Asla Yalan Söylemez!
Matematik Asla Yalan Söylemez!
eXTReMe Tracker
Finding and Removing Loop on a Singly-Linked List
Category: C / C++
Date: 06.02.2008 12:02:52


One of the most common interview questions for software professionals is "How do you find a loop in a singly linked list?". Most of the people tend to think in the recursive way to solve this problem. The truth is that the most optimal solution for this problem lies out of the scope of the linked list.

A singly linked list is a common data structure familiar to all computer scientists. A singly linked list is made of nodes where each node has a pointer to the next node (or null to end the list). On a linked list, adding a new fist element, removing the existing first element, and examining the first element are very fast O(1) operations.

When working with singly linked list, you are typically given a link to the first node. Common operations on a singly linked list are iterating through all the nodes, adding to the list, or deleting from the list. Algorithms for these operations generally require a well formed linked list. That is a linked list without loops or cycles in it.

If a linked list has a cycle:

• The malformed linked list has no end (no node ever has a null next_node pointer)
• The malformed linked list contains two links to some node
• Iterating through the malformed linked list will yield all nodes in the loop multiple times

A malformed linked list with a loop causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list is malformed before trying an iteration. This article is a discussion of various algorithms to detect a loop in a singly linked list.


Incorrect "Solutions"

Mark Each Node

Traverse the list and mark each node as having been seen. If you come to a node that has already been marked, then you know that the list has a loop.

// Incorrect 'solution'
function boolean hasLoop(Node startNode){
  Node currentNode = startNode;
  do {
    if (currentNode.seen) return true;
    currentNode.seen = true;
  } while (currentNode = currentNode.next());
  return false;
}

The problem with this solution is ensuring that "seen" is marked as false for all the nodes before you start. If the linked list has a loop, it isn't possible to iterate over each node to set "seen" to "false" as an initial value for each node.

Even if you are able to solve the initial value problem, each node in a linked list may not have a field to use for this purpose. Requiring such a field in each node would mean that this is not a generic solution. As we will see later, this field in not needed for a perfectly correct and efficient solution anyway.

Detect Only Full Loops

When asked to come up with a solution, a common pitfall is not detecting all loops, but just a loop where the last node links to the first. A loop could still occur (and not be detected) if the last element linked to (for example) the second element.

// Incorrect 'solution'
function boolean hasLoop(Node startNode){
  Node currentNode = startNode;
  while (currentNode = currentNode.next()){
    if (currentNode == startNode) return true;
  }
  return false;
}


Most Common Inefficient Solution

Keep a hash set of all nodes seen so far (O(n) time complexity, O(n) space complexity)

Keeping a set of all the nodes have seen so far and testing to see if the next node is in that set would be a perfectly correct solution. It would run fast as well. However it would use enough extra space to make a copy of the linked list. Allocating that much memory is prohibitively expensive for large lists.

// Inefficient solution
function boolean hasLoop(Node startNode){
  HashSet nodesSeen = new HashSet();
  Node currentNode = startNode;
  do {
    if (nodesSeen.contains(currentNode)) return true;
    nodesSeen.add(currentNode);
  } while (currentNode = currentNode.next());
  return false;
}


Best Solutions

Catch Larger and Larger Loops (O(n) time complexity)

Always store some node to check. Occasionally reset this node to avoid the "Detect Only Full Loops" problem. When resetting it, double the amount of time before resetting it again.

// Good solution
function boolean hasLoop(Node startNode){
  Node currentNode = startNode;
  Node checkNode = null;
  int since = 0;
  int sinceScale = 2;
  do {
    if (checkNode == currentNode) return true;
    if (since >= sinceScale){
        checkNode = currentNode;
        since = 0;
        sinceScale = 2*sinceScale;
    }
    since++;
  } while (currentNode = currentNode.next());
  return false;
}

This solution is O(n) because sinceScale grows linearly with the number of calls to next(). Once sinceScale is greater than the size of the loop, another n calls to next() may be required to detect the loop. This solution requires up to 3 traversals of the list.

This solution was devised by Stephen Ostermiller and proven O(n) by Daniel Martin.

Catch Loops in Two Passes (O(n) time complexity)

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

Robert W. Floyd discoverd the Floyd's cycle-finding algorithm in 1967 based on the properties of the pseudo-random sequences. By applying this algorithm, we simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.


How to remove the loop?

It's obvious now to detect a loop. But how to remove the loop in the linked list? Goal is to locate the place where the loop is occurring and set that node's next to null.

It's actually continuation of the detection process. Once the first two pointers have met, ie., a loop has been detected, freeze the first pointer, and set other pointer pointing to the head, advance these two by 1 step each till the next node to each is the same. The position of the second pointer points to the node that is expected to be the tail, and hence its next should be set to NULL.

But actually it will not work for circlic linked lists, so we need a modification on the algorithm.

Here is the code that I have written for both, does detection and removal. Test code is included, so you can compile and run for testing. I have tested for there cases: No loop case, one loop in the middle case and circlic case, it's OK.

#include 

typedef enum { FALSE, TRUE } bool;

/* Declaration of Node type */
typedef struct node_s {
	int data;
	struct node_s *next;
} node_t;

/*
** Detection: Have two pointers into the list (ptr and depar). Advance depar twice as
** fast as ptr; if they ever point to the same place then the list
** has a loop in it.
**
** Removal: Leave one pointer(depar) in place where the two pointers in the previous
** step met, and another pointer(ptr) pointing to the head, advance these two by 1 step
** each till the next node to each is the same. The node pointer with depar will be the
** last node, so set it's next to NULL.
*/
bool findAndRemoveLoop (node_t *head)
{
	node_t *ptr = head;
	node_t *depar = head;
	bool ret = FALSE;		// the return value
	
	// this loop detects the loop
	while (depar) {
		ptr = ptr->next;
		if ((depar = depar->next) && (depar = depar->next) && depar == ptr) {
			ret = TRUE;
			break;
		}
	}
	
	// this part removes the loop
	if (ret == TRUE) {
		ptr = head;
		while(ptr->next != depar->next) {
			ptr = ptr->next;
			depar = depar->next;
		}
		if(ptr == depar) {	    // note that this means it's a circlic list
			// iterate through the last (prev) node
			while(depar->next != ptr) {
				depar = depar->next;
			}
		}
		depar->next = NULL;	// this points to the last node
	}
	
	return ret;
}


////////////////////// TEST CODE ///////////////////////


node_t nodearr[10];

void initNodes()
{
	int i;
	
	// initialize the nodes
	for(i = 0; i < 10; i++) {
		nodearr[i].data = i;
		nodearr[i].next = NULL;
	}
}

void printList(node_t *head)
{
	int limit = 20;
	while(head && (--limit)) {
		printf("%d->",head->data);
		head = head->next;
	}
	printf("\n");
}

int main()
{
	int i;
	node_t * head;
	
	initNodes();
	
	// establish the linked list
	for(i = 0; i < 9; i++) {
		nodearr[i].next = &nodearr[i+1];
	}
	head = &nodearr[0];
	
	// Scenario 1: No loop
	printf("Scenario 1: No loop\n");
	printList(head);
	printf("Scenario 1: After removal\n");
	findAndRemoveLoop(head);
	printList(head);
	
	// Scenario 2: Loop from node 5	
	// let's have the list loop from node 5
	nodearr[9].next = &nodearr[4];
	printf("Scenario 2: Loop from node 5\n");
	printList(head);
	findAndRemoveLoop(head);
	printf("Scenario 2: After removal\n");
	printList(head);
	
	// Scenario 3: Circlic list
	nodearr[9].next = &nodearr[0];
	printf("Scenario 3: Circlic list\n");
	printList(head);
	findAndRemoveLoop(head);
	printf("Scenario 3: After Removal\n");
	printList(head);	
	
	return 0;
}

Download Code

I hope it helps you. :))

Links & References

Comments

No comments posted yet.



© Copyright. All rights reserved. Designed by Bilal Hatipoğlu. RSS Feed  Valid W3C XHTML 1.0 Document  Valid W3C CSS Document