## Reverse a Linked List – Part 2

This post is the extension of our earlier post Reverse a linked list. Here We have provided the better recursive solution in which we start reversing the list from the end.

Objective: Reverse the given linked list.

Example:

```Original List :->10->8->6->4->2
Reversed List :->2->4->6->8->10```

Approach:

## Swap Every Kth Node in a LinkedList

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

```Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10
```

Approach:

## Delete a Node in the Middle of a linked list, Given only access to that Node

Objective: Write a program to Delete a Node in the Middle of a linked list, Given only access to that Node

Example:

```Original List : ->1->2->8->3->7->0->4
After Deleting the mid node (say 7) : ->1->2->8->3->0->4
```

Output: Linked list with deleted node

Approach:

• Approach is tricky and simple
• Copy the value of next node to the node which you want to delete
• Delete the next node

## Find the n’th Node from the end of a given Linked List

Objective: Given a linked list and integer ‘n’, write an algorithm to find the nth node from the end in the Linked List.

Example:

```Original List : ->1->2->8->3->7->0->4
Output : 3rd Element from the end is : 7
```

Input: An unsorted linked list and integer k

Output: The kth to Last Element of a Singly Linked List

Approach:

Read moreFind the n’th Node from the end of a given Linked List

## Remove Duplicates from an Unsorted Linked list

Objective: Write a program to remove the duplicates from an unsorted linked list

Example:

```Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3
```

Output: Linked list with no duplicates.

Approach:

• Create a Hash Map
• Take two pointers, prevNode and CurrNode.
• PrevNode will point to the head of the linked list and currNode will point to the head.next.

## Check if one string is Rotation of another string

Objective: Write an algorithm to check if one string is Rotation of another string. This question has been asked in the Amazon interview.

Example:

```Input Strings : 'sumitjain' and 'tjainsumi'
Output : true

Input String : 'Jaain' and 'ainJ'
Output: false
```

Input: Two Strings

Output: True or false based on whether strings are rotation of each other.

Approach:

Read moreCheck if one string is Rotation of another string

## String Compression using count of repeated characters – Run Length Encoding

Objective: Write an algorithm to compress the given string by using the count of repeated characters and if new compressed string length is not smaller than the original string then return the original string.

Example:

```Input String : ssssuuuummmmmmiiiittttttttttttt
Compressed String : s4u4m6i4t13

Input String : Jaain
Compressed String : Jaain (Since compressed string is length is greater than original string)
```

Input: A String

Output: either A compressed string or original string whichever us smaller.

Approach:

Read moreString Compression using count of repeated characters – Run Length Encoding

## Replace all spaces in a String with ‘%20’

Objective: Write an algorithm to replace all spaces in a given string with ‘%20’. You can consider that string has enough space at the end of the string to hold the extra characters.

Input: A String and true length of a string

Output: Updated string in which each space is replaced by the ‘%20’

```Example:

Input String : I am Sumit Jain

Output String : I%20am%20Sumit%20Jain

```

Approach:

Read moreReplace all spaces in a String with ‘%20’

## Find Whether Two Strings are Permutation of each other

Objective: Given Two Strings, check whether one string is permutation of other

Input: Two Strings

Output: True or false based on whether strings are permutation of other or not.

Example:

```"sumit" and "tiums" are permutations of each other.

"abcd" and bdea" are not permutations of each other.

```

Approach:

Read moreFind Whether Two Strings are Permutation of each other

## Find Intersection Point in Two Linked List

Objective: Given Two linked list, check whether both list intersect each other, if yes then find the starting node of the intersection.

Intersection point means end of one linked list is linked with some node in another linked list and it forms a Y shape.

Output: Intersection Node or point

Example:

Approach:

## Find the Loop in a Linked list, find its length and Break the Loop

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

```Example:

Input : ->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30

here you can see that 30->40->50->60 are repeating ,that means it has a loop
```

Approach:

Read moreFind the Loop in a Linked list, find its length and Break the Loop

## Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

Objective: Count all the paths from left top corner to right bottom corner in two dimensional array.

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

Recursive solution to this problem is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub problems which will be solved again and again to get the final solution. read this : “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Read moreCount All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

## Merge or Combine Two Sorted Linked Lists

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

```Example:

List a : ->2->6->18

Listb: ->1->3->17->19

Merged List: ->1->2->3->6->17->18->19
```

Approach: