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

1. Create a Node that is equal to the first node in the linked list
2. 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.
3. 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;
}

void removeDuplicates( Node * head ) {

return;
}

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;
}
}

{

cout << "List is: ";

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

int main(){

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

// Insert somemore values

cout << endl;

cout << "Linked List after Removal of Duplicates: " << endl;

// 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

1. Move ptr1 ahead knth spots ahead from the beginning and ptr2
2. With ptr1 ahead by knth spots, move ptr1 along linked list untill the end and update the positions of ptr2
3. 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;
}

void deleteList( Node * & head ) {
Node * nextNode;
}
}

void printList( Node * head ) {
}
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

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() {

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

std::cout << "4th node from last (Iterative) : " << std::endl;

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

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;
}

void deleteList( Node * & head ) {
Node * nextNode;
}
}

void printList( Node * head ) {
}
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 node; // returns node to kthToLastRecursive
}

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

int main() {

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

std::cout << "List: ";

std::cout << "4th node from last (Recursive) : ";
if ( node4 != nullptr ) {
std::cout << node4->data << std::endl;
} else {
std::cout << "NULL NODE\n";
}
std::cout << "List: ";

}
``````

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:

2. Free up Memory (space)

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

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

2. 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;
}

void deleteList( Node * & head ) {
Node * nextNode;
}
}
{
Node* temp1 = head;  // Point to first element in the linked list

if (n == 1)
{
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 ) {
}
std::cout << "null" << std::endl;
}

int main() {

std::cout << "List Before Deleting Node 1 " <<  std::endl;

std::cout << std::endl;

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

std::cout << std::endl;

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

}
``````

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

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;
}

void printList( Node * head ) {
}
std::cout << "nullptr" << std::endl;
}

// Iterative solution to reversing Linked List

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

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

// iterative solution

return true;
}

// Find the Middle NOde

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

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(middleNode);

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

}

int main(){

std::cout << "List 1: ";

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

std::cout << "List 2: ";
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;
}

void printList( Node * head ) {
}
std::cout << "nullptr" << std::endl;
}

// Iterative solution to reversing Linked List

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

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

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

//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(){

std::cout << "List 1: ";

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

std::cout << "List 2: ";
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

1. Find the Lengths of both List 1 and 2
2. Set longer list to ptr1 and shorter list to ptr2
3. If needed (List 1 being longer), adjust pointer ahead so we have equal lengths
4. 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 ) {
}
std::cout << "nullptr" << std::endl;
}

// return the length of the list passed in
int count = 0;
count += 1;
}
return count;
}

// find length of both linked lists

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

// 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
``````
``````

Updated: