### 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.

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

class Solution
{
public:
//Function to reverse a linked list.
struct Node* reverseList(struct Node *head)
{
struct Node* prev = NULL;
struct Node* curr = head;
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).

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

class Solution
{
public:
struct node *reverse (struct node *head, int k)
{
if (!head) return NULL;
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)
head->next = reverse(next, k);
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution
{
public:
//Function to check if the linked list has a loop.
bool detectLoop(Node* head)
{
while(head)
{
if(head->data == INT_MIN)
return true;
head->data = INT_MIN;
head = head -> next;
}
return false;
}
};

#### Optimal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution
{
public:
//Function to check if the linked list has a loop.
bool detectLoop(Node* head)
{
Node *slow = head, *fast = head;
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)**

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

int getNthFromLast(Node *head, int n)
{
int size = 0;
Node *l = head;
Node *r = head;
while(n--){
if(!r) return -1;
r = r->next;
}
while(r) {
r = r->next;
l = l->next;
}
return l->data;
}