Merge two sorted lists

Merge two sorted lists



/*
  Merge two sorted lists A and B as one linked list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* MergeLists(Node *headA, Node* headB)
{
  // This is a "method-only" submission. 
  // You only need to complete this method 
    Node *tmpA = headA, *tmpB = headB, *headC, *tmpC, x;
    headC = &x;
    headC -> next = NULL;
    tmpC = headC;
    while(tmpA != NULL && tmpB != NULL)
        {
        if(tmpA -> data <= tmpB -> data )
            {
            Node *t = tmpA;
            tmpA = tmpA -> next;
            tmpC -> next = t;
            t -> next = NULL;
            }
        else 
            {
            Node *t = tmpB;
            tmpB = tmpB -> next;
            tmpC -> next = t;
            t -> next = NULL;            
        }
        tmpC = tmpC -> next;
    }   
    if(tmpA == NULL)
        tmpC -> next = tmpB;
    if(tmpB == NULL)
        tmpC -> next = tmpA;
    return headC -> next;
}

Detect cycle in linked list

Problem Statement

This challenge is part of a tutorial track by MyCodeSchool

You’re given the pointer to the head node of a linked list. Find whether the list contains any cycle (or loop). A linked list is said to contain cycle if any node is re-visited while traversing the list. The head pointer given may be null meaning that the list is empty.

Input Format 
You have to complete the int HasCycle(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console. Number of nodes in a linked list doesn't exceed 100.

Output Format 
Check whether the linked list has a cycle and return 1 if there is a cycle. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

1 --> NULL

1 --> 2 --> 3
      ^     |
      |     |
       -----                           

Sample Output

0
1

Explanation 
1. First list has no cycle, hence return 0 
2. Second list is shown to have a cycle, hence return 1.

Note 
After first solving the problem by yourself, see Floyd's cycle-finding algorithm for an efficient solution which uses O(N) time and O(1) additional memory.

Copyright © 2015 HackerRank.
All Rights Reserved

/*
  Detect loop in a linked list 
  List could be empty also
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
int HasCycle(Node* head)
{
   // Complete this function
   // Do not write the main method
    Node *hare = head, *tor = head;
    if(head == NULL)
        return 0;
    while(1)
        {
        if(hare -> next == NULL)
            return 0;
        if(hare -> next -> next == NULL)
            return 0;
        hare = hare -> next -> next;
        tor = tor -> next;
        if(tor == hare)
            return 1;
    }
}

Compare two linked lists

Problem Statement

This challenge is part of a tutorial track by MyCodeSchool

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format 
You have to complete the int CompareLists(Node* headA, Node* headB) method which takes two arguments - the heads of the two linked lists to compare. You should NOT read any input from stdin/console.

Output Format 
Compare the two linked lists and return 1 if the lists are equal. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

NULL, 1 --> NULL 
1 --> 2 --> NULL, 1 --> 2 --> NULL

Sample Output

0
1

Explanation 
1. We compare an empty list with a list containing 1. They don't match, hence return 0. 
2. We have 2 similar lists. Hence return 1.

Copyright © 2015 HackerRank.
All Rights Reserved

• ITERATIVE

/*
  Compare two linked lists A and B
  Return 1 if they are identical and 0 if they are not. 
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
int CompareLists(Node *headA, Node* headB)
{
  // This is a "method-only" submission. 
  // You only need to complete this method 
    Node *tmpA = headA, *tmpB = headB;
    while(tmpA != NULL && tmpB != NULL)
        {
        if(tmpA -> data != tmpB -> data)
            return 0;
        else
            {
            tmpA = tmpA -> next;
            tmpB = tmpB -> next;
        }
    }
    if(tmpA == NULL && tmpB == NULL)
        return 1;
    else
        return 0;
}

• RECURSIVE

/*

  Compare two linked lists A and B

  Return 1 if they are identical and 0 if they are not. 

  Node is defined as 

  struct Node

  {

     int data;

     struct Node *next;

  }

*/

int CompareLists(Node *headA, Node* headB)

{

  // This is a "method-only" submission. 

  // You only need to complete this method 

    if(headA == NULL && headB == NULL)

        return 1;

    if(headA != NULL && headB != NULL)

        {

        if(headA -> data != headB -> data)

            return 0;

        else 

            return CompareLists(headA -> next , headB -> next);

    }

    else

        return 0;

}

Reverse linked list - iterative

Reverse linked list





/*
  Reverse a linked list and return pointer to the head
  The input list will have at least one element  
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* Reverse(Node *head)
{
    if(head == NULL)
        return head;
    Node *z = NULL;
    Node *x = head;
    Node *y = x -> next;
    x -> next =  NULL;
    while(y != NULL)
        {
        z = y -> next;
        y -> next = x;
        x = y;
        y = z;
    }
    head = x;
    return head;
}

Palindrome index

Problem Statement

You are given a string of lower case letters. Your task is to figure out the index of the character on whose removal it will make the string a palindrome. There will always be a valid solution.

In case the string is already a palindrome, then -1 is also a valid answer along with possible indices.

Input Format

The first line contains T, i.e. the number of test cases.
T lines follow, each containing a string.

Output Format

Print the position (0 index) of the letter by removing which the string turns into a palindrome. For a string, such as

bcbc

we can remove b at index 0 or c at index 3. Both answers are accepted.

Constraints
1≤T≤20
1≤ length of string ≤100005
All characters are Latin lower case indexed.

Sample Input

3
aaab
baa
aaa

Sample Output

3
0
-1

Explanation

In the given input, T = 3,

• For input aaab, we can see that removing b from the string makes the string a palindrome, hence the position 3.
• For input baa, removing b from the string makes the string palindrome, hence the position 0.
• As the string aaa is already a palindrome, you can output 0, 1 or 2 as removal of any of the characters still maintains the palindrome property. Or you can print -1 as this is already a palindrome.

JAVA Program 

import java.io.*;
import java.util.*;

public class Solution {
    
    public static int isPallindrome(String string){
        for(int i = 0; i< string.length()/2 ; i++){
            if(string.charAt(i) != string.charAt(string.length() - i -1)){
                return 0;
            }
        }
        return 1;
    }
    public static int pallindromeIndex(String string, int start, int end){
        if(start >= end-1){
            return -1;
        }else{
            if(string.charAt(start) == string.charAt(end-1)){
                return pallindromeIndex(string, start + 1, end - 1);
            }else{
                String temp = string.substring(start , end -1 );
                if(isPallindrome(temp) == 1){
                    return end - 1;
                }else{
                    return start;
                }
            }
        }
       
    }
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int K = in.nextInt();
        for(int i = 0; i<K; i++){
            String string = in.next();
            int index = pallindromeIndex(string, 0, string.length());
            System.out.println(index);
        }
    }
}

================================================================

C Program :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t, i;
    scanf("%d",&t);
    for( i = 0 ; i < t ; i ++ )
        {
        char *in;
        int len, j, k, index = -1; 
        scanf("%ms",&in);
        len = strlen(in);
        j = 0;
        k = len - 1; 
        while( j < len/2 )
            {
            if( in[k] != in[j] )
                {
                if( in[j + 1] == in[k] && in[k - 1] != in[j] )
                    {
                    index = j;
                    break;
                }
                else if( in[j + 1] != in[k] && in[k - 1] == in[j])
                    {
                    index = k;
                    break;
                }               
                else 
                    {
                    int l;
                    for( l = 2 ; j+l < len/2 && in[j+l] == in[k-l-1] ; l++);
                    if(j+l == len/2)
                        {
                        index = k;
                        break;
                    }
                    for( l = 3 ; j+l <= len/2 && in[j+l] == in[k-l+1] ; l++);
                    if(j+l == len/2 + 1)
                        {
                        index = j;
                        break;
                    }
                    
                }
                    
            }
            j++;
            k--;
        }
            printf("%d\n",index);
    }
    return 0;
}