Linked List Problems

13 minute read

Many of these problems involving linked lists can be solved using either a runner or recursion.

Remove Duplicates from a Linked List

How do you remove duplicates from a linked list ???

For Example:

5->7->9->8->7->6->5->4->3->2->1->0->

to:

5->7->9->8->6->4->3->2->1->0->

Where we remove the duplicate value of 5 and 7!

Logic

How do we plan to remove duplicates? Well the basic logic is

Create a Node that is equal to the first node in the linked list
We move along in the linked list checking each node data/value for our current node, if equal we set the node were on to the next next node, else we move along the linked list.
We check every single node in the linked list for duplicate

#include<iostream>
using std::cout;
using std::endl;

struct Node{
    int data;
    Node* next;
};

void Insert( Node * &head, int x){

    Node*temp = new Node();
    temp->data = x;
    temp->next = head;
    head = temp;
}

void removeDuplicates( Node * head ) {

	if ( head == nullptr || ( head && (head->next == nullptr))) {
		return;
	}
    
	Node * curr = head;

	while(curr) {

		Node * runner = curr;

		while (runner->next != nullptr) {

			if (runner->next->data == curr->data) {
                cout << "Values  that duplicate: " << runner->next->data << endl;
				runner->next = runner->next->next;  // set link and fix
                cout << "Removing Duplicate which is: " << curr->data << endl;

			} else {
                // Else if
				runner = runner->next;
			}
		}
		curr = curr->next;
	}
}


void print(Node * &head)
{
    Node* temp = head; // ADddre of the head node

    cout << "List is: ";

    while(temp != NULL){
        //iterate through
        cout << temp->data << "->";
        temp = temp->next;
    }
    cout << endl;
}

int main(){

    Node* head = NULL;

    for (int i = 0; i < 10; i++){
        Insert(head, i);
    }

    // Insert somemore values
    Insert(head, 7);  // Duplicate
    Insert(head, 5);  // Duplicate

    print(head);
   
    cout << endl;

    removeDuplicates(head);

    cout << "Linked List after Removal of Duplicates: " << endl;
    print(head);

    // Lets remove any "Duplicates" using the function removed duplicates

}

Output

List is: 5->7->9->8->7->6->5->4->3->2->1->0->

Values  that duplicate: 5
Removing Duplicate which is: 5
Values  that duplicate: 7
Removing Duplicate which is: 7
Linked List after Removal of Duplicates: 
List is: 5->7->9->8->6->4->3->2->1->0->

Return the Kth to Last

Can Perform both Iteratively and Recursivily

Iteratively Solution

STEPS:

For this example we will use pointers to mark positions

Move ptr1 ahead knth spots ahead from the beginning and ptr2
With ptr1 ahead by knth spots, move ptr1 along linked list untill the end and update the positions of ptr2
Therefore at the end ptr2 will be knth spots behind and we can return the value!!!

#include <iostream>

struct Node{
    int data;
    Node* next;
};

void insert( Node * &head, int data){

    Node*temp = new Node();
    temp->data = data;
    temp->next = head;
    head = temp;
}


void deleteList( Node * & head ) {
  Node * nextNode;
  while(head) {
    nextNode = head->next;
    delete(head);
    head = nextNode;
  }
}

void printList( Node * head ) {
  while(head) {
    std::cout << head->data << "-->";
    head = head->next;
  }
  std::cout << "null" << std::endl;
}


Node * kthToLastIterative( Node * head, int k ) {
  // Return node at the k nth position

  if ( head == nullptr ) {
    return head; // Empty List so return
  }

  Node * ptr1 = head;  // Two Pointers to keep track
  Node * ptr2 = head;

  int i = 0;

  while( i < k && ptr1 ) {
    // Move ptr1 k spots ahead!
    ptr1 = ptr1->next; 
    ++i;
  }
  // Out of Bounds
  if ( i < k ) {
    return nullptr;
  }
  while( ptr1 != nullptr ) {
    // move until ptr1 is at end
    // ptr2 will be in the correct position!
    ptr1 = ptr1->next;
    ptr2 = ptr2->next;
  }
  return ptr2;
}



int main() {

  Node * head = nullptr; // Starting Address

  for ( int i = 9; i > 0; i-- ) {
    insert(head, i);
  }
  std::cout << "List: ";
  printList(head);

  std::cout << "4th node from last (Iterative) : " << std::endl;
  Node *node4 = kthToLastIterative(head, 4);

  if ( node4 != nullptr ) {
    std::cout << "Node at 4th spot is: " << node4->data << std::endl;
  } else {
    std::cout << "NULL NODE\n";
  }
  // deleteList(head);
  std::cout << "List: ";
  printList(head);
}

Output:

List: 1-->2-->3-->4-->5-->6-->7-->8-->9-->null
4th node from last (Iterative) : 
Node at 4th spot is: 6
List: 1-->2-->3-->4-->5-->6-->7-->8-->9-->null

Recursive Solution

#include <iostream>

struct Node{
    int data;
    Node* next;
};

void insert( Node * &head, int data){

    Node*temp = new Node();
    temp->data = data;
    temp->next = head;
    head = temp;
}


void deleteList( Node * & head ) {
  Node * nextNode;
  while(head) {
    nextNode = head->next;
    delete(head);
    head = nextNode;
  }
}

void printList( Node * head ) {
  while(head) {
    std::cout << head->data << "-->";
    head = head->next;
  }
  std::cout << "null" << std::endl;
}


Node * kthToLastHelper( Node * head, int k , int & i) {
  if ( head == nullptr ) {
    return nullptr;
  }
  
  Node * node = kthToLastHelper(head->next, k, i);

  i = i + 1;

  //if we have solved problem k times from last.
  if ( i == k ) { // Exit condition!
    return head;
  }

  return node; // returns node to kthToLastRecursive
}

Node * kthToLastRecursive( Node * head, int k ) {
  int i = 0;
  return kthToLastHelper(head, k, i);  // Recursive call
}

int main() {

  Node * head = nullptr; 

  for ( int i = 9; i > 0; i-- ) {
    insert(head, i);
  }

  std::cout << "List: ";
  printList(head);
  
  std::cout << "4th node from last (Recursive) : ";
  Node *node4 = kthToLastRecursive(head, 4);
  if ( node4 != nullptr ) {
    std::cout << node4->data << std::endl;
  } else {
    std::cout << "NULL NODE\n";
  }
  // deleteList(head);
  std::cout << "List: ";
  printList(head);

}

Output:

List: 1-->2-->3-->4-->5-->6-->7-->8-->9-->null
4th node from last (Recursive) : 
6
List: 1-->2-->3-->4-->5-->6-->7-->8-->9-->null

Delete a Node at the Nth position

Delete Node at any position

Tips for Solving

Example:

a->b->c->d->e->NULL

Lets Delete c!

a->b->d->e->NULL

What to do:

Fix Links/Next
Free up Memory (space)

There are two types of Scenario that we can run into.

Scenario 1: if the node to be deleted is the 1st node!
Scenario 2: if the node to be deleted is not the first node.

a.) Loop until you’re at the node before the node that is to be removed.

b.) Create a new temp node (temp2) that’s equal to the Node to be removed

c.) Set temp1 node tp point to node after our node to be removed

d.) Delete temp2 node (which is the node we want to remove at nth index)

Code

 #include <iostream>

struct Node{
    char data;
    Node* next;
};

void insert( Node * &head, char data){

    Node*temp = new Node();
    temp->data = data;
    temp->next = head;
    head = temp;
}


void deleteList( Node * & head ) {
  Node * nextNode;
  while(head) {
    nextNode = head->next;
    delete(head);
    head = nextNode;
  }
}
void delete_at(Node* &head, char n)
{
    Node* temp1 = head;  // Point to first element in the linked list
    
    if (n == 1)
    {
        head = temp1->next; 
        delete(temp1); 
        return; 
    }



    for (int i = 0; i < n-2; i++ )
    {
        temp1 = temp1->next;
    }
    // Loop 
    Node* temp2 = temp1->next; // nth Node

    temp1->next = temp2->next; // (n+1)th Node


    delete(temp2); // Delete temp2

}

void printList( Node * head ) {
  while(head) {
    std::cout << head->data << "-->";
    head = head->next;
  }
  std::cout << "null" << std::endl;
}

int main() {

  Node * head = nullptr; 
  insert(head, 'a');
  insert(head, 'b');
  insert(head, 'c');
  insert(head, 'd');
  insert(head, 'e');




  std::cout << "List Before Deleting Node 1 " <<  std::endl;
  printList(head);

  delete_at(head,1);
  std::cout << std::endl;

  std::cout << "List after Deleting Node 1 (e is deleted)" << std::endl;
  printList(head);


  delete_at(head,3);
std::cout << std::endl;


  std::cout << "List after deleting Node in 3rd Position (b is deleted) " << std::endl;

  printList(head);
}

Output:

List Before Deleting Node 1 
e-->d-->c-->b-->a-->null

List after Deleting Node 1 (e is deleted)
d-->c-->b-->a-->null

List after deleting Node in 3rd Position (b is deleted) 
d-->c-->a-->null

Partition Problem

Add Lists (Sum Lists)

Problem: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, write a function that adds the two numbers and returns the sum as a linked list.

Example

Input: (7-> 1-> 6) + (5-> 9-> 2). Which is 617 + 295 Output: (2-> 1-> 9). Which is 912!

Can do both recursively and iteratively

Code

Check if a Linked List is a Palindrome

Different Ways to solve this problem both iterativley and recusively
Can be solved with Recusively with or without a stack

Palindrome Recursively without Stack

#include <iostream>

struct Node{
    int data;
    Node* next;
};

void insert( Node * &head, int data){

    Node*temp = new Node();
    temp->data = data;
    temp->next = head;
    head = temp;
}

void printList( Node * head ) {
  while ( head ) {
    std::cout << head->data << "-->";
    head = head->next;
  }
  std::cout << "nullptr" << std::endl;
}

void reverse(Node * &head ){

    // Iterative solution to reversing Linked List

    Node *current, *next, *previous;
    current = head;
    previous = NULL;

    while ( current != NULL){
        next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    head = previous;
}

bool isPalindrome( Node *head){

    // iterative solution

    if (head == NULL || head->next == NULL){
        return true;
    }


    // Find the Middle NOde
    Node* ptr1 = head;
    Node* ptr2 = head;

    Node * middleNode = NULL;

    while (ptr1 && ptr2 && ptr1->next ) {
        // while true, basically untill last value we should move ptr1 ahead two times so ptr2 is in the middle
        ptr1 = ptr1->next->next;
        ptr2 = ptr2->next;
    }

    // Watch out for odd numbers 
    // in case skip middle node
    if (ptr1 && ptr1->next == NULL){
        ptr2 = ptr2->next;
    }
    // Reverse second half of the linked list, pass address of ptr2 to reverse
    reverse(ptr2);

    middleNode = ptr2;

    // Lets now compare the two halves
    ptr1 = head; // Start of our orginal linked list again

    while (ptr1 && ptr2 && ptr1->data == ptr2->data ){
        // While we move move through the first half the linked list (ptr) and the second half (ptr2) we check 
        // if the data values match
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }

    // reverse linked list again
    reverse(middleNode);

    // Check if ptr2 is
    if ( ptr2 == NULL ) {
         return true;
    } 
    else {
        return false;
    }

}


int main(){

  Node * head1 = NULL;
  insert( head1, 1 );
  insert( head1, 2 );
  insert( head1, 3 );
  insert( head1, 3 );
  insert( head1, 2 );
  insert( head1, 1 );
  std::cout << "List 1: ";
  printList(head1);

    if ( isPalindrome(head1) ) {
    std::cout << "List 1 is pallindrome list\n";
  } else {
    std::cout << "List 1 is not a pallindrome list\n";
  }
  std::cout << std::endl;
  
  // not a palidrone

  Node* head2 = NULL;
  insert( head2, 4 );
  insert( head2, 2 );
  insert( head2, 3 );
  insert( head2, 3 );
  insert( head2, 2 );
  insert( head2, 1 );
  std::cout << "List 2: ";
  printList(head2);
   if ( isPalindrome(head2) ) {
    std::cout << "List 2 is pallindrome list\n";
  } else {
    std::cout << "List 2 is not a pallindrome list\n";
  }
}

Output

List 1: 1-->2-->3-->3-->2-->1-->nullptr
List 1 is pallindrome list

List 2: 1-->2-->3-->3-->2-->4-->nullptr
List 2 is not a pallindrome list

Palindrome Recursively with Stack

#include <iostream>
#include <stack>

struct Node{
    int data;
    Node* next;
};

void insert( Node * &head, int data){

    Node*temp = new Node();
    temp->data = data;
    temp->next = head;
    head = temp;
}



void printList( Node * head ) {
  while ( head ) {
    std::cout << head->data << "-->";
    head = head->next;
  }
  std::cout << "nullptr" << std::endl;
}

void reverse(Node * &head ){

    // Iterative solution to reversing Linked List

    Node *current, *next, *previous;
    current = head;
    previous = NULL;

    while ( current != NULL){
        next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    head = previous;
}

bool isPalindrome( Node * head ) {
    // Use Stack to Check
  // if list is empty or just contains one node.
  if ( head == nullptr || head->next == nullptr ) {
    return true;
  }

  Node * ptr1 = head;
  Node * ptr2 = head;

  //pushing the first half of list to stack.
  std::stack<Node*> nodeStack;

  while( ptr2 && ptr1 && ptr1->next ) {
    ptr1 = ptr1->next->next;
    nodeStack.push(ptr2);
    ptr2 = ptr2->next;
  }

  //in case of odd number of nodes, skip the middle one
  if ( ptr1 && ptr1->next == nullptr ) {
    ptr2 = ptr2->next;
  }
  // Now compare the other half of the list with nodes
  // we just pushed in stack

  while(!nodeStack.empty() && ptr2) {

      // pop and remove from stack and 
      // compare with the second half of the linked list
    Node * curr = nodeStack.top();
    std::cout << "Current: " << curr->data << std::endl;
    nodeStack.pop();
    if (curr->data != ptr2->data) {
      return false;
    }
    ptr2 = ptr2->next;
  }

  return true;
}


int main(){

  Node * head1 = NULL;
  insert( head1, 1 );
  insert( head1, 2 );
  insert( head1, 3 );
  insert( head1, 3 );
  insert( head1, 2 );
  insert( head1, 1 );
  std::cout << "List 1: ";
  printList(head1);

    if ( isPalindrome(head1) ) {
    std::cout << "List 1 is pallindrome list\n";
  } else {
    std::cout << "List 1 is NOT a pallindrome list\n";
  }
  std::cout << std::endl;
  
  // not a palidrone

  Node* head2 = NULL;
  insert( head2, 4 );
  insert( head2, 2 );
  insert( head2, 3 );
  insert( head2, 3 );
  insert( head2, 2 );
  insert( head2, 1 );
  std::cout << "List 2: ";
  printList(head2);
   if ( isPalindrome(head2) ) {
    std::cout << "List 2 is pallindrome list\n";
  } else {
    std::cout << "List 2 is NOT a pallindrome list\n";
  }

}

Output

List 1: 1-->2-->3-->3-->2-->1-->nullptr
Current: 3
Current: 2
Current: 1
List 1 is pallindrome list

List 2: 1-->2-->3-->3-->2-->4-->nullptr
Current: 3
Current: 2
Current: 1
List 2 is NOT a pallindrome list

Palindrome Recursive Solution

Given Two singly linked lists, check if the two lists Intersect

Intersection is not necessary the same value, it’s the same Memory Address

Steps/Logic

Find the Lengths of both List 1 and 2
Set longer list to ptr1 and shorter list to ptr2
If needed (List 1 being longer), adjust pointer ahead so we have equal lengths
Traverse the linked list with our pointers (ptr1 and ptr2 ) and check for equality (equal memory address)

#include <iostream>

struct Node {
  int data;
  Node * next;
  Node( int d ) : data{ d }, next{ nullptr } { } // Constructor: Used in new keyword!
};

void printList( Node * head ) {
  while ( head ) {
    std::cout << head->data << "-->";
    head = head->next;
  }
  std::cout << "nullptr" << std::endl;
}

int listlength(Node* head){
    // return the length of the list passed in
    int count = 0;
    while (head){
        count += 1;
        // Update head to next
        head = head->next;
    }
    return count;
}

Node * IntersectionPoint(Node* head1, Node* head2){
    // find length of both linked lists
    int len1 = listlength(head1);
    int len2 = listlength(head2);

    // Find the bigger and smaller list set bigger list to ptr1 and smaller to ptr2

    Node* ptr1 = (len1 > len2) ? head1 : head2;
    Node* ptr2 = (len1 > len2 ) ? head2 : head1;

    // Possibly adjust ptr1 if list 1 is longer than list 2
    int i = 0;
    while (i < std::abs(len1 - len2) && ptr1 ){
        ptr1 = ptr1->next;
        ++i;
    }

    // Traverse over the two lists using ptr1 and ptr2 and compare their address to see if they intersect
    while(ptr1 && ptr2 ){
        
        if (ptr1 == ptr2){
            
            return ptr1; // if eqaul address we found the intersection
    }
      ptr1 = ptr1->next;
      ptr2 = ptr2->next;
    }

    return NULL;
}

int main(){

    // Create Lists
    // List One
  Node * list1 = new Node(1);
  list1->next = new Node(2);
  list1->next->next = new Node(3);
  list1->next->next->next = new Node(9);
  list1->next->next->next->next = new Node(3);
  list1->next->next->next->next->next = new Node(2);
  
  // List Two
  Node * list2 = new Node(12);
  list2->next = new Node(8);
  list2->next->next = list1->next->next->next;

  std::cout << "List 1: ";
  printList(list1);
  std::cout << "List 2: ";
  printList(list2);



  Node * intersectingNode = IntersectionPoint( list1 , list2 );

  if (intersectingNode) {
    
    std::cout << "Intersecting Node of lists is : " << intersectingNode->data << std::endl;
  } else {
    
    std::cout << "Lists do not interset" << std::endl;
  }
}

Output:

List 1: 1-->2-->3-->9-->3-->2-->nullptr
List 2: 12-->8-->9-->3-->2-->nullptr
Intersecting Node of lists is : 9

Check for Loop Detection in Linked List

Check out

Share on

Twitter Facebook LinkedIn

Devin Powers

Linked List Problems

Remove Duplicates from a Linked List

Return the Kth to Last

Delete a Node at the Nth position

Partition Problem

Add Lists (Sum Lists)

Check if a Linked List is a Palindrome

Palindrome Recursively without Stack

Palindrome Recursively with Stack

Palindrome Recursive Solution

Given Two singly linked lists, check if the two lists Intersect

Check for Loop Detection in Linked List

Share on

You may also enjoy

Intro to RabbitMQ

Intro to FastAPI

Introduction to K8s using Minikube

Zoom Data Engineering Part 6