# Acing Linked List Problems

--

In this blog, I will be covering important problems on the linked list so that after going through this blog you will be good enough to ace linked list problems in your interview.I have shared the most optimized, well commented and most easisest way of writing code for each problem.

**Problem 1: Add last in Linked list**

In our linked list we will be having a head pointer and a tail pointer. So we will be making use of these pointers to add node in the last of a linked list

void addLast(int val) {

//Firstly make a node containing this value

ListNode * newNode = new ListNode(val);

//Now check if linked list is empty

if (head == NULL) {

//In this case newNode will be the head and tail

head = newNode;

tail = newNode;

}

//Linked list is not empty

else {

tail -> next = newNode;

tail = tail -> next;

}

}

**Problem 2: Display a linked list**

void displayList() {

//If linked list is empty

if (head == NULL)

return;//Store head of linked list in a temp variable

ListNode * temp = head;

while (temp != NULL) {

cout << temp -> val << “ “;

//Move temp to next node

temp = temp -> next;

}

}

We have made use of the temp variable here because we don’t want to lose the head pointer of our linked list!

**Problem 3: Remove first in Linked List**

We have to remove the head node in this problem. Let’s see the solution.

void removeFirst() {

//If linked list is empty

if (head == NULL) {

cout << “List is empty”;

return;

}//If linked list contains single element

if (head == tail) {

delete head;

head = NULL;

tail = NULL;

} else {

ListNode * temp = head -> next;

delete head;

head = temp;

}

}

**Problem 4: Get Value At Given Index in Linked List**

int getValue(int index) {

//If linked list is empty

if (head == NULL) {

return -1;

}ListNode * temp = head;

//Will discuss that how to identify <index or equal to index

for (int i = 0; i < index; i++) {

//This means index passed is more than the size of linked list

if (temp == NULL) {

cout << “Invalid Arguments”;

return -1;

}

temp = temp -> next;

}

return temp -> val;

}

Now let’s discuss that how to think of condition in for loop.In question we will be given index of which we have to return data.Now we know that index starts from 0.See when i = 0 then temp = head so on i=0 we are transferring pointer to node at index (i+1) i.e 1.Suppose we are asked value at index 3.If our i beacomes 3 then we will be transferring pointer to 4.But we want pointer to be at 3 so i should always be less than index passed in the question.

**Problem 4: Add First in Linked List**

In this problem we have to add the node at head of a linked list

void addFirst(int val) {

//Make a node with this value

ListNode * newNode = new ListNode(val);

//Now check if linked list is empty

if (head == NULL) {

head = newNode;

tail = newNode;

} else {

//This new node should point to previous head node

newNode -> next = head;

//New node has become the head node

head = newNode

}

}

**Problem 5: Add at given index in Linked List**

In this problem we have to add the node at the index provided in the parameter.

void addAtGivenIndex(int index, int val) {

//Make a new node

ListNode * newNode = new ListNode(val);

ListNode * temp = head;for (int i = 0; i < (index — 1); i++) {

//Index is more than the size of the linked list

if (temp == NULL) {

cout << “Invalid index passed”;

return;

}

temp = temp -> next;

}//If linked list is empty and index passed is 0.In this case if index passed is other than 0 then our upper for loop will handle

if (temp == NULL) {

head = newNode;

tail = newNode;

return;

}

//Now new node should point at the previous node at index parameter passed

newNode -> next = temp -> next;

temp -> next = newNode;

}

**Problem 6: Reverse a linked list**

Here we will be discuusing various ways to reverse a linked list

** Method 1: **We will be writing a iterative function and will be using the data property of nodes for reversing a linked list i.e whole nodes will not be reversed only the data inside nodes will be reversed.

Here we will be making use of the function getNodeAt the given index.

void reverseLL() {

//Pointer at start index

int li = 0;

//Pointer at end index

int ri = size — 1;//Keep swapping the values until there remains only one element in linked list

while (li <= ri) {

Node left = getNodeAt(li);

Node right = getNodeAt(ri);int temp = left.data;

left.data = right.data;

right.data = temp;li++;

ri — ;

}

}

}

** Method 2 : **In

**this method**

**function will be an iterative function and will be reversing the contents of linked list by changing the “next” property of nodes.**

We will take three pointers curr, next and prev.

ListNode* reverseList(ListNode* head) {

if(head == NULL){

return head;

}

ListNode* curr = head;

ListNode* prev = NULL;

ListNode* next = NULL;

while(curr != NULL){

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

}

return prev;

}

** Method 3: **This method of reversing a linked list is useful in solving many good linked list problems.This is almost same as method 2 but here we will not need prev pointer as we will be adding nodes in the front of a newly created linked list.Let’s see this in code.

ListNode* reverseList(ListNode* head) {

if(head == NULL || head->next == NULL){

return head;

}

ListNode* curr = head;

ListNode* next = NULL;

ListNode* newHead = NULL;

ListNode* newTail = NULL;

while(curr != NULL){

next = curr->next;

if(newHead == NULL){

curr->next = NULL;

newHead = curr;

newTail = curr;

}

else{

curr->next = newHead;

newHead = curr;

}

curr = next;

}

return newHead;

}

*Method 4:**In this method we will be reversing linked list using recursion.*

ListNode* reverseList(ListNode* head) {

//Base Case

if(head == NULL || head->next == NULL){

return head;

}

//Recursive calls

ListNode* tempHead = reverseList(head->next);

//attaching the previous head to the last of linked list brought by recursion

head->next->next = head;

head->next = NULL;

//return newHead

return tempHead;

}

**Problem 7:**** Reverse Nodes in K-Groups**

Given a linked list, reverse the nodes of a linked list *k* at a time and return its modified list.This is a really nice question.Do try it on leetcode.

ListNode * reverseKGroup(ListNode * head, int k) {

//Edge cases

if (head == NULL || head -> next == NULL || k == 0 || k == 1) {

return head;

}//Getting the size of the linked list

int size = 0;

ListNode * temp = head;

while (temp != NULL) {

temp = temp -> next;

size++;

}//In this list we will be storing our final answer

ListNode * originalHead = NULL;

ListNode * originalTail = NULL;

ListNode * curr = head;

ListNode * next = NULL;//Now when size is greater than or equal to K

while (size >= k) {

int count = k;

ListNode * tempHead = NULL;

ListNode * tempTail = NULL;//Reversing K elements at a time

while (count > 0) {

count — ;

next = curr -> next;

if (tempHead == NULL) {

tempHead = curr;

tempTail = curr;

} else {

curr -> next = tempHead;

tempHead = curr;

}

curr = next;

}//Putting the reversed K element into our anwer linked list

if (originalHead == NULL) {

originalHead = tempHead;

originalTail = tempTail;

} else {

originalTail -> next = tempHead;

originalTail = tempTail;

}

size -= k;

}if (originalTail != NULL)

originalTail -> next = curr;//updating the original Tail

if (curr != NULL) {

while (curr -> next != NULL) {

curr = curr -> next;

}

originalTail = curr;

}return originalHead;

}

**Problem 8: Kth Node from a linked list**

In this problem we need to return the kth node from the last of a linked list.This is also a nice problem.I will make use of slow and fast pointers here and will not be making use of size property.The concept we are using in it is that suppose you and me are running on a 200m track.Initially I am standing at 0 and you are standing at 20m.We both starting running at same speed.Now it’s obvious that you will win the race.But the thing of our attention is that since we were maintaing a gap of 20m initially so when you will be reaching the end of track, I will be exactly 20m away from the end of the track.This same concept we will use here!

ListNode * KthNode(int k) {

if (head == NULL) {

return NULL;

}ListNode * slow = head;

ListNode * fast = head;

//Putting fast pointer at K distance

for (int i = 0; i < k; i++) {

fast = fast -> next;

}//Until fast pointer reaches the end of the linked list

while (fast != NULL) {

slow = slow -> next;

fast = fast -> next;

}return slow;

}

**Problem 9:****Middle Of a Linked List**

Given the head of a singly linked list, return the middle node of the linked list.If there are two middle nodes, return the second middle node.

ListNode* middleNode(ListNode* head) {

if(head == NULL){

return head;

}

//Take two pointers.Slow will jump by and fast will jump by 2

ListNode* slow = head;

ListNode* fast = head;

while(fast != NULL && fast->next != NULL){

slow = slow->next;

fast = fast->next->next;

}

return slow;

}

fast!= NULL condition will hit first in case of odd sized linked list while the fast->next != NULL condition will hit in case of even sized linked list.

**Problem 10: ****Merge sort a linked list**

We have to sort a linked list using merge sort here.

ListNode * sortList(ListNode * head) {

ListNode * mergeList(ListNode * head1, ListNode * head2) {

if (head1 == NULL && head2 == NULL) {

return head1;

}if (head1 == NULL) {

return head2;

}if (head2 == NULL) {

return head1;

}//Make a dummy linked list

ListNode * resultHead = new ListNode(0);

ListNode * resultTail = resultHead;//traverse through both the lists

while (head1 != NULL && head2 != NULL) {

if (head1 -> val < head2 -> val) {

ListNode * newNode = new ListNode(head1 -> val);

resultTail -> next = newNode;

resultTail = newNode;

head1 = head1 -> next;

// resultTail->next = head1;

// resultTail = head1;

// resultTail->next = NULL;

// head1 = head1->next;

} else {

ListNode * newNode = new ListNode(head2 -> val);

resultTail -> next = newNode;

resultTail = newNode;

head2 = head2 -> next;

// resultTail->next = head2;

// resultTail = head2;

// resultTail->next = NULL;

// head2 = head2->next;

}

}//Now put the remaining nodes

while (head1 != NULL) {

ListNode * newNode = new ListNode(head1 -> val);

resultTail -> next = newNode;

resultTail = newNode;

head1 = head1 -> next;

}while (head2 != NULL) {

ListNode * newNode = new ListNode(head2 -> val);

resultTail -> next = newNode;

resultTail = newNode;

head2 = head2 -> next;

}

return resultHead -> next;}

ListNode * findMid(ListNode * head) {

if (head == NULL) {

return head;

}//Take two pointers.Slow will jump by and fast will jump by 2

ListNode * slow = head;

ListNode * fast = head;

ListNode * prev = NULL;

while (fast != NULL && fast -> next != NULL) {

prev = slow;

slow = slow -> next;

fast = fast -> next -> next;

}return prev;

}ListNode * sortList(ListNode * head) {

//Base case

if (head == NULL || head -> next == NULL) {

return head;

}//Find mid node of a linked list

ListNode * mid = findMid(head);//Dividing the list into two parts

ListNode * newHead = mid -> next;

mid -> next = NULL;//Recursive calls

ListNode * head1 = sortList(head);

ListNode * head2 = sortList(newHead);//merge these two sorted lists

ListNode * result = mergeList(head1, head2);

return result;}

}

Some important points here:

We have made a dummy linked list here so that we do not have to check the condition that linked list is empty or not before adding a new node in a linked list.

Here while finding a mid pointer we have kept a prevSlow pointer and returned this instead of slow pointer.Why this is so?Dry run a case with two nodes in a linked list.You will get the reason.Hint: mid+1 will be creating a runtime error.

**Problem 11:Is linked list a palindrome?**

We are required to check if the linked list is a palindrome or not and return true or false accordingly.

Here we will making use of recursion stack.

bool isPalindromeHelper(ListNode* head){

if(head == NULL){

return true;

}

bool ans = isPalindromeHelper(head->next)&&(left->val == head->val);

left = left->next;

return ans;

}

ListNode* left;

bool isPalindrome(ListNode* head) {

left = head;

return isPalindromeHelper(head);

}

**Problem 12: Fold a linked list**

In this problem we have to connect last node after first node, secondLast node after second node and so on…

Example

1->2->3->4->5

will fold as

1->5->2->4->3

We will use the same concept as we have used in problem 11.

void foldLLHelper(ListNode * head, int floor, int size) {

//Base Case

if (head == NULL) {

return;

}//Recursive call

foldLLHelper(head -> next, floor + 1);

//While returnng from recursion

if (floor > size / 2) {

ListNode * temp = left -> next;

left -> next = head;

head -> next = temp;

}

//We have reached last node of folded linked list

else if (floor == size / 2) {

head — next = NULL;

}

left = left -> next;

}//This pointer will traverse linked list from starting

ListNode * left = head;

void foldLL(ListNode * head) {

if (head == NULL || head -> next == NULL)

return;//Finding size of linked list

int size = 0;

ListNode * temp = head;

while (head != NULL) {

temp = temp -> next;

size++;

}

foldLLHelper(head, 0, size);

}

**Problem 13: Add two linked lists**

We will be provided with two linked lists and we have to return resultant linked list after addition of two.

This problem has two variation.Let’s discuss both.

** First Variation: **The function is passed two linked lists which represent two numbers — the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list.

The following approaches are not allowed :

1.** Don’t reverse the linked lists** in order to access them from least significant digit

to most significant.

2. Don’t use arrays or explicit extra memory.

3. Don’t convert linked lists to number, add them up and convert the result back

to a linked list.

int addTwoHelper(Node* one, Node* two, int v1, int v2, linkedlist& res){

if(one == NULL && two == NULL){

return 0;

}

int carry;

int addResult;

if(v1 < v2){

carry = addTwoHelper(one, two->next, v1, v2–1, res);

addResult = (two->data+carry);

}

else if(v1 > v2){

carry = addTwoHelper(one->next, two, v1–1, v2, res);

addResult = (one->data+carry);

}

else{

carry = addTwoHelper(one->next, two->next, v1–1, v2–1, res);

addResult = (one->data+two->data+carry);

}

res.addFirst(addResult%10);

return (addResult/10);

}linkedlist addTwoLists(linkedlist one, linkedlist two) {

linkedlist res;

int c =addTwoHelper(one.head, two.head, one.size, two.size, res);

if(c > 0){

res.addFirst(c);

}

return res;

}

**Second Variation:**** **You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode* dummy = new ListNode(0);

ListNode* result = dummy;

int carry = 0;

while(l1 != NULL || l2 != NULL){

int val1 = l1 == NULL ? 0 : l1->val;

int val2 = l2 == NULL ? 0 :l2->val;

int res = (val1+val2+carry);

int x = res%10;

carry = res/10;

ListNode* newNode = new ListNode(x);

result->next = newNode;

result= newNode;

if(l1 != NULL)

l1 = l1->next;

if(l2 != NULL)

l2 = l2->next;

}

if(carry > 0){

result->next = new ListNode(carry);

}

return dummy->next;

}

**Problem 14: Intersection of two linked lists**

Given the heads of two singly linked-lists, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return NULL.

Example: **Input:** intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3**Output:** Intersected at ‘8’

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

//Getting size of both linked lists

int size1 = 0;

int size2 = 0;

ListNode* temp1 = headA;

ListNode* temp2 = headB;

while(temp1 != NULL){

temp1 = temp1->next;

size1++;

}

while(temp2 != NULL){

temp2 = temp2->next;

size2++;

}

temp1 = headA;

temp2 = headB;

//The head pointer of bigger linked list should be moved so that it’s size can become equal to shorter linked list

if(size1 > size2){

for(int i = 0; i < abs(size1-size2); i++){

temp1 = temp1->next;

}

}

else{

for(int i = 0; i < abs(size1-size2); i++){

temp2 = temp2->next;

}

}

//Now start traversing until you found exactly same nodes

while(temp1 != NULL){

if(temp1 == temp2){

return temp1;

}

temp1 = temp1->next;

temp2 = temp2->next;

}

//Intersection node does not exist

return NULL;

}

So here we comes at the end of this blog.If this blog has helped you in any way then do give this post a clap.Do share this post with your friends because knowledge is a thing that increases exponentially on sharing.Happy Coding!