by Priyanshu Tiwari

## Table Of Content

### Reverse a string #

The task is to complete the function reverseList() with head reference as the only argument and should return new head after reversing the list.

class Solution
{
public:
//Function to reverse a linked list.
{
struct Node* prev = NULL;
while(curr!=NULL){
struct Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

};



### Reverse a Linked List in groups of given size #

Given a linked list of size N. The task is to reverse every k nodes (where k is an input to the function) in the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should be considered as a group and must be reversed (See Example 2 for clarification).

class Solution
{
public:
struct node *reverse (struct node *head, int k)
{

node *current = head, *next = NULL, *prev = NULL;
int count(0);

while (current != NULL && count++ < k) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}

if (next)

return prev;
}
};


### Detect Loop in linked list #

Given a linked list of N nodes. The task is to check if the linked list has a loop. Linked list can contain self loop.

#### Brute #

class Solution
{
public:
//Function to check if the linked list has a loop.
{
{
return true;
}
return false;
}
};


#### Optimal #

class Solution
{
public:
//Function to check if the linked list has a loop.
{
while(slow && fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow==fast)
return true;
}
return false;
}
};


### Nth node from end of linked list #

Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.

Initialize two pointers to head. Move the right pointer n times and then move move both the pointer untill the right reaches the end. Now the left pointer points to the nth node from the end.

• Time Complexity : O(n)
• Space Complexity : O(1)
int getNthFromLast(Node *head, int n)
{
int size = 0;

while(n--){
if(!r) return -1;
r = r->next;
}

while(r) {
r = r->next;
l = l->next;
}

return l->data;
}