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!