Singly Linked List

Chenglei Si
Sep 7, 2018 · 3 min read

See explanation of finding loop port in linked list below the codes.

//Basic Operations of Singly Linked List
//Define Node class
template <typename Type> class Node{
public:
Type data;
Node<Type> *next;
Node(const Type &_data){
data=_data;
next=NULL;
}
};

//Define Linked List class
template <typename Type> class LinkedList{
private:
Node<Type> *head;
public:
LinkedList(){
head=NULL;
}

//delete the entire list
~LinkedList(){
Node<Type> *current_node=head;
while(current_node!=NULL){
Node<Type> *delete_node=current_node;
current_node=current_node->next;
delete delete_node;
}
}

//insert a node pointer (need to allocate memory before inserting)
void insert(Node<Type> *node, int index){
//special case 1: empty list
if(head==NULL){
if(index!=0){
return;
}
head=node;
return;
}
//special case 2: insert the head
if(index==0){
node->next=head;
head=node;
return;
}
//general case: first find the node before the target position
Node<Type> *current_node=head;
int count=0;
//the last position can be inserted in a[length], so cur cannot be beyond the last element
while(current_node->next!=NULL&&count<index-1){
current_node=current_node->next;
count++;
}
//make sure the index is legal, then insert
if(count==index-1){
node->next=current_node->next;
current_node->next=node;
}
}

void output(){
if(head==NULL){
return;
}
Node<Type> *current_node=head;
while(current_node!=NULL){
cout<<current_node->data<<" ";
current_node=current_node->next;
}
cout<<endl;
}

void delete_node(int index){
if(head==NULL){
return;
}
Node<Type> *current_node=head;
int count=0;
if(index==0){
head=head->next;
delete current_node;
return;
}
//find the position before index
while(current_node->next!=NULL&&count<index-1){
current_node=current_node->next;
count++;
}
//unlike insert, cannot delete after the last node
if(count==index-1&&current_node->next!=NULL){
Node<Type> *delete_node=current_node->next;
current_node->next=delete_node->next;
delete delete_node;
}
}


//find node by value
Node<Type>* find_node(Type value){
Node<Type> *current_node=head;
while(current_node!=NULL){
if(current_node->data==value){
return current_node;
}
current_node=current_node->next;
}
return NULL;
}

//find node by index
Node<Type>* find_ith_node(int index){
int count=0;
Node<Type> *current_node=head;
while(count<index&&current_node->next!=NULL){
current_node=current_node->next;
count++;
}
if(count==index&&current_node!=NULL){
return current_node;
}
return NULL;
}


//reverse linked list
void reverse(){
if(head==NULL||head->next==NULL){
return;
}
Node<Type> *next_node,*current_node;
current_node=head->next;
//detach head
head->next=NULL;
//point current_node to head, update it to be new head
while(current_node!=NULL){
next_node=current_node->next;
current_node->next=head;
head=current_node;
current_node=next_node;
}
}

//Floyd's Cycle Detection
bool has_loop(){
Node<Type> *fast=head,*slow=head;
//two ways to stop:
//fast meets NULL: no cycle
//fast meets slow: has cycle
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast) break;
}
return !(fast==NULL||fast->next==NULL);
}


//find the starting node of the loop
//see detailed math explanation at the end
Node<Type>* find_loop_port(){
Node<Type> *fast=head,*slow=head;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast) break;
}
if(fast==NULL||fast->next==NULL){
return NULL;
}
//slow starts from head again and fast moves with slow
//they meet again at loop port
slow=head;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}

//find loop length
int loop_length(){
Node<Type> *fast=head,*slow=head;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast) break;
}
if(fast==NULL||fast->next==NULL){
return 0;
}
int count=0;
//let slow go one more round to count length
do{
slow=slow->next;
count++;
}while(slow!=fast);
return count;
}

};


//example test code
int main(){
LinkedList<int> linkedlist;
for(int i=0;i<5;i++){
Node<int> *node=new Node<int>(i+1);
linkedlist.insert(i,node);
}
}

Explanation of loop port finding

alt text
alt text

Suppose slow pointer moves s steps, then fast pointer has moved 2s steps when they meet. Suppose the length of the loop is r, the distance from head to loop port is a , and the distance from the loop port to the meeting point is x.

Since fast pointer moves closer to slow by one step every time the slow pointer moves one step, and the max chasing distance between the two is (r-1), the fast pointer can meet slow pointer by a maximum of (r-1) steps. In other words, when two pointers meet, the slow pointer is still at its first traversal of the loop. Suppose when they meet, the fast pointer has already travelled n loops.

We have:

2s = s + nr (distance travelled by fast)

s = nr

a + x = nr (distance travelled by slow)

a + x = (n-1)r + r = (n-1)r + (L-a)

a = (n-1)r + (L -a -x)

(L -a-x) is the distance from meeting point to the loop port. So if we let two pointers start from head and meeting point respectively and move one step at a time , they will meet at the loop port.