Swap Nodes of Linked List without Copying

C++ Code:

void swap_nodes(Node **headPtr, int a, int b){

    if(a == b || !headPtr || !(*headPtr))

        return;

    

    Node *curr = *headPtr;

    Node *prev = nullptr;

    Node *nodeA = nullptr;

    Node *nodeB = nullptr;

    Node *prevA = nullptr;

    Node *prevB = nullptr;

    

    while (curr) {

        if(curr->data == a){

            nodeA = curr;

            prevA = prev;

        } else if(curr->data == b){

            nodeB = curr;

            prevB = prev;

        }

        prev = curr;

        curr = curr->next;

    }

    

    if(!nodeA || !nodeB)

        return;

    

    if(prevA){

        prevA->next = nodeB;

    } else { // nodeA is head

        *headPtr = nodeB;

    }

    

    if(prevB){

        prevB->next = nodeA;

    } else { // nodeB is head

        *headPtr = nodeA;

    }

    

    Node *tmp = nodeA->next;

    nodeA->next = nodeB->next;

    nodeB->next = tmp;

}

Detailed explanation is available on youtube:  

Subscribe toKnowledgeCenter 

Check if a Linked List is palindrome

Detailed explanation is available on youtube: 

Subscribe to KnowledgeCenter

Remove Loop From Linked List using Floyd's Algorithm

C++ Code:

void remove_loop(Node *head){

    Node *slow = head;

    Node *fast = head;

    if (!head || !(head->next))

        return;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast)

            break;

    }

    

    // No Loop exixts

    if (slow != fast){

        std::cout << "No Loop" << std::endl;

        return;

    }

    

    // When Loop exists

    slow = head;

    while(slow->next != fast->next){

        slow = slow->next;

        fast = fast->next;

    }

    fast->next = nullptr;

}

Detailed explanation is available on Youtube:

Subscribe to KnowledgeCenter

Why Floyd's Loop Detection Algorithm works ?

For detailed Explanation watch the youtube video:

Subscribe to KnowledgeCenter

Find First Element of Loop in Linked List

C++ Code:

void find_loop_beginning(Node *head){

    Node *slow = head;

    Node *fast = head;

    if (!head || !(head->next))

        return;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast)

            break;

    }

    

    // No Loop exixts

    if (slow != fast){

        std::cout << "No Loop" << std::endl;

        return;

    }

    

    // When Loop exists

    slow = head;

    while(slow != fast){

        slow = slow->next;

        fast = fast->next;

    }

    std::cout << "First loop element = " << slow->data << std::endl;

}

Detailed explanation can be found on Youtube:

Subscribe to KnowledgeCenter

Find k-th node from end in Linked List

void print_kth_from_end(Node *head, int k){

    Node *lead = head;

    Node *lag = head;

    while(k > 0){

        if(lead){

            k--;

            lead = lead->next;

        }

        else{

            std::cout << "K is larger than length of Linked List" << std::endl;

            return;

        }

    }

    while(lead){

        lead = lead->next;

        lag = lag->next;

    }

    std::cout << "kth node from end = " << lag->data << std::endl;

}

Detailed explanation can be found on Youtube:

Subscribe to KnowledgeCenter

Find the middle element of a Linked List

void print_middle(Node *head){

    Node *fast = head;

    Node *slow = head;

    while(fast && fast->next){

        fast = fast->next->next;

        slow = slow->next;

    }

    std::cout << slow->data << std::endl;

}

Watch the detailed explanation of the concepts on Youtube:

Subscribe to KnowledgeCenter

Reinforcement Learning : Introduction

Characteristics:

1. No Supervisor, Reward signal
2. Delayed Feedback
3. Data depends on Agent's actions

Examples:

1. Learning to play chess
2. Making a robot walk
3. Fly stunt manoeuvres in Helicopter

Reward (Rt):

• A scalar feedback signal
• Indicates how well agent is doing at time t
• Agent tries to maximize cumulative Reward over time

E.g.,

• Chess : +ve reward for winning the game, -ve for losing
• Robot walk : +ve for forward movement, -ve for falling
• Helicopter manoeuvres : +ve for following trajectory, -ve for crashing

Sequential Decision Making:

• Select actions to maximize total future rewards
• Long-term consequences
• May need to sacrifice immediate rewards for better Long-term rewards

E.g.,

Some moves in chess, financial investments

Agent and Environment:

At each step t, the Agent:

• Executes action At
• Receives observation Ot
• Receives scalar reward Rt

Environment:

• Receives action At
• Emits observation Ot+1
• Emits reward Rt+1

t increments at environment step

Detailed explanation and illustrative examples can be found on Youtube:

Subscribe to KnowledgeCenter

History & State:

History:

• A sequence of Observations, Actions and Rewards that the Agent has seen so far.

            Ht = A1, O1, R1, ….., At, Ot, Rt

• All observable variables up to time t

• What happens next depends on the history:
• Agent(our Algorithm) selects Actions
• Environment selects Observations/Rewards

State:

• History is not very useful as it's a very long stream of data.

• State is the information used to determine what happens next.

• Function of History

St = f(Ht)

E.g, take only last 3 observations

Environment/World State:

• State of environment used to determine how to generate next Observation and Reward.

• Usually not accessible to Agent.

• Even if visible, may not have any information useful for Agent

Agent State:

• Agent's internal representation

• Information used by Agent(our algorithm) to pick next Action

• Can be any function of History

Markov Assumption:

• Information State: State used by Agent is a sufficient statistic of History. In order to predict the future you only only need the current state of the environment.

• State St is Makov if and only if:

P(St+1|St, At) = P(St+1|S1,S2,..,St, At)

• Future is independent of Past given Present

• E.g., State defined by a Trading Algorithm used by HFT traders.
• 
  

Detailed explanation and illustrative examples can be found on Youtube:

Subscribe to KnowledgeCenter

Environment :

Fully Observable Environment:

• Agent directly observes environment state

           O(t) = Sa(t) = Se(t)

• Agent State = Environment State

• Markov Decision Process(MDP)

Partially Observable Environment:

• Agent indirectly observes Environment:
• A HFT trader observes only current prices
• A robot with camera vision doesn't observe its absolute location
• Poker playing agent observes only public cards

• Agent State != Environment State

• Partially Observable Markov Decision Process (POMDP)

• Agent has to construct its own representation of State

E.g.,

• Sa(t) = H(t)
• Sa(t) = (P[Se(t) = s1],....., P[Se(t) = sn])
• Sa(t) = f(Sa(t-1), O(t))

Detailed description can be found on youtube:

Subscribe to KnowledgeCenter

Find the Length of Loop in Linked List

We modify the Floyd's Loop/Cycle Detection Algorithm that we saw in the previous Post to find the count of Nodes which are part of the Linked List.

int count_loop_lenth(Node *node){

    int count = 1;

    Node *curr = node;

    while(curr->next != node){

        curr = curr->next;

        ++count;

    }

    return count;

}

int detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast){

            return count_loop_lenth(slow);

        }

    }

    return 0;

}

Watch detailed Explanation on Youtube.

Subscribe to KnowledgeCenter

Detect Loop in a Linked List

Method 1: (Hashing)

bool detect_loop_map(Node *head){

    std::unordered_map<Node*, bool> visited;

    Node *curr = head;

    while(curr){

        if (visited[curr] == true)

            return true;

        visited[curr] = true;

        curr = curr->next;

    }

    return false;

}

Method 2:(Floyd's Cycle Detection)

bool detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if (slow == fast){

            return true;

        }

    }

    return false;

}

Watch detailed explanation on Youtube:

Visit our Youtube playlist for Linked List: https://www.youtube.com/playlist?list=PL1w8k37X_6L-bwZCPpELH6Cwo3WzUxDp7

Subscribe to KnowledgeCenter