In this HackerRank Find Merge Point of Two Lists Interview preparation kit problem, You have Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
class SinglyLinkedListNode:
def __init__(self, node_data):
self.data = node_data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_node(self, node_data):
node = SinglyLinkedListNode(node_data)
if not self.head:
self.head = node
else:
self.tail.next = node
self.tail = node
def print_singly_linked_list(node, sep, fptr):
while node:
fptr.write(str(node.data))
node = node.next
if node:
fptr.write(sep)
# Complete the findMergeNode function below.
#
# For your reference:
#
# SinglyLinkedListNode:
# int data
# SinglyLinkedListNode next
#
#
def findMergeNode(headA, headB):
while headA:
node = headB
while node:
if headA == node:
return headA.data
node = node.next
headA = headA.next
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
tests = int(input())
for tests_itr in range(tests):
index = int(input())
llist1_count = int(input())
llist1 = SinglyLinkedList()
for _ in range(llist1_count):
llist1_item = int(input())
llist1.insert_node(llist1_item)
llist2_count = int(input())
llist2 = SinglyLinkedList()
for _ in range(llist2_count):
llist2_item = int(input())
llist2.insert_node(llist2_item)
ptr1 = llist1.head;
ptr2 = llist2.head;
for i in range(llist1_count):
if i < index:
ptr1 = ptr1.next
for i in range(llist2_count):
if i != llist2_count-1:
ptr2 = ptr2.next
ptr2.next = ptr1
result = findMergeNode(llist1.head, llist2.head)
fptr.write(str(result) + 'n')
fptr.close()
Problem solution in Java Programming.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
}
public static void printSinglyLinkedList(SinglyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));
node = node.next;
if (node != null) {
bufferedWriter.write(sep);
}
}
}
// Complete the findMergeNode function below.
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode next;
* }
*
*/
static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
SinglyLinkedListNode temp1=head1;
SinglyLinkedListNode temp2=head2;
List<SinglyLinkedListNode>list=new ArrayList<SinglyLinkedListNode>();
while(temp1!=null){
list.add(temp1);
temp1=temp1.next;
}
while(temp2!=null){
if(list.contains(temp2)){
break;
}
temp2=temp2.next;
}
return temp2.data;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int tests = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int testsItr = 0; testsItr < tests; testsItr++) {
int index = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
SinglyLinkedList llist1 = new SinglyLinkedList();
int llist1Count = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int i = 0; i < llist1Count; i++) {
int llist1Item = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
llist1.insertNode(llist1Item);
}
SinglyLinkedList llist2 = new SinglyLinkedList();
int llist2Count = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int i = 0; i < llist2Count; i++) {
int llist2Item = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
llist2.insertNode(llist2Item);
}
SinglyLinkedListNode ptr1 = llist1.head;
SinglyLinkedListNode ptr2 = llist2.head;
for (int i = 0; i < llist1Count; i++) {
if (i < index) {
ptr1 = ptr1.next;
}
}
for (int i = 0; i < llist2Count; i++) {
if (i != llist2Count-1) {
ptr2 = ptr2.next;
}
}
ptr2.next = ptr1;
int result = findMergeNode(llist1.head, llist2.head);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
Problem solution in C++ programming.
#include <bits/stdc++.h>
using namespace std;
class SinglyLinkedListNode {
public:
int data;
SinglyLinkedListNode *next;
SinglyLinkedListNode(int node_data) {
this->data = node_data;
this->next = nullptr;
}
};
class SinglyLinkedList {
public:
SinglyLinkedListNode *head;
SinglyLinkedListNode *tail;
SinglyLinkedList() {
this->head = nullptr;
this->tail = nullptr;
}
void insert_node(int node_data) {
SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
if (!this->head) {
this->head = node;
} else {
this->tail->next = node;
}
this->tail = node;
}
};
void print_singly_linked_list(SinglyLinkedListNode* node, string sep, ofstream& fout) {
while (node) {
fout << node->data;
node = node->next;
if (node) {
fout << sep;
}
}
}
void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;
free(temp);
}
}
// Complete the findMergeNode function below.
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode* next;
* };
*
*/
int findMergeNode(SinglyLinkedListNode* headA, SinglyLinkedListNode* headB) {
while(headA){
SinglyLinkedListNode *tmp = headA->next;
headA->next = NULL;
headA = tmp;
}
while(headB){
if(headB->next == NULL){
return headB->data;
}
headB = headB->next;
}
return 0;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
int tests;
cin >> tests;
cin.ignore(numeric_limits<streamsize>::max(), 'n');
for (int tests_itr = 0; tests_itr < tests; tests_itr++) {
int index;
cin >> index;
cin.ignore(numeric_limits<streamsize>::max(), 'n');
SinglyLinkedList* llist1 = new SinglyLinkedList();
int llist1_count;
cin >> llist1_count;
cin.ignore(numeric_limits<streamsize>::max(), 'n');
for (int i = 0; i < llist1_count; i++) {
int llist1_item;
cin >> llist1_item;
cin.ignore(numeric_limits<streamsize>::max(), 'n');
llist1->insert_node(llist1_item);
}
SinglyLinkedList* llist2 = new SinglyLinkedList();
int llist2_count;
cin >> llist2_count;
cin.ignore(numeric_limits<streamsize>::max(), 'n');
for (int i = 0; i < llist2_count; i++) {
int llist2_item;
cin >> llist2_item;
cin.ignore(numeric_limits<streamsize>::max(), 'n');
llist2->insert_node(llist2_item);
}
SinglyLinkedListNode* ptr1 = llist1->head;
SinglyLinkedListNode* ptr2 = llist2->head;
for (int i = 0; i < llist1_count; i++) {
if (i < index) {
ptr1 = ptr1->next;
}
}
for (int i = 0; i < llist2_count; i++) {
if (i != llist2_count-1) {
ptr2 = ptr2->next;
}
}
ptr2->next = ptr1;
int result = findMergeNode(llist1->head, llist2->head);
fout << result << "n";
}
fout.close();
return 0;
}
Problem solution in C programming.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
typedef struct SinglyLinkedListNode SinglyLinkedListNode;
typedef struct SinglyLinkedList SinglyLinkedList;
struct SinglyLinkedListNode {
int data;
SinglyLinkedListNode* next;
};
struct SinglyLinkedList {
SinglyLinkedListNode* head;
SinglyLinkedListNode* tail;
};
SinglyLinkedListNode* create_singly_linked_list_node(int node_data) {
SinglyLinkedListNode* node = malloc(sizeof(SinglyLinkedListNode));
node->data = node_data;
node->next = NULL;
return node;
}
void insert_node_into_singly_linked_list(SinglyLinkedList** singly_linked_list, int node_data) {
SinglyLinkedListNode* node = create_singly_linked_list_node(node_data);
if (!(*singly_linked_list)->head) {
(*singly_linked_list)->head = node;
} else {
(*singly_linked_list)->tail->next = node;
}
(*singly_linked_list)->tail = node;
}
void print_singly_linked_list(SinglyLinkedListNode* node, char* sep, FILE* fptr) {
while (node) {
fprintf(fptr, "%d", node->data);
node = node->next;
if (node) {
fprintf(fptr, "%s", sep);
}
}
}
void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;
free(temp);
}
}
// Complete the findMergeNode function below.
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode* next;
* };
*
*/
int findMergeNode(SinglyLinkedListNode* headA, SinglyLinkedListNode* headB) {
while(headA){
SinglyLinkedListNode *tmp = headA->next;
headA->next = NULL;
headA = tmp;
}
while(headB){
if(headB->next == NULL){
return headB->data;
}
headB = headB->next;
}
return 0;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char* tests_endptr;
char* tests_str = readline();
int tests = strtol(tests_str, &tests_endptr, 10);
if (tests_endptr == tests_str || *tests_endptr != '') { exit(EXIT_FAILURE); }
for (int tests_itr = 0; tests_itr < tests; tests_itr++) {
char* index_endptr;
char* index_str = readline();
int index = strtol(index_str, &index_endptr, 10);
if (index_endptr == index_str || *index_endptr != '') { exit(EXIT_FAILURE); }
SinglyLinkedList* llist1 = malloc(sizeof(SinglyLinkedList));
llist1->head = NULL;
llist1->tail = NULL;
char* llist1_count_endptr;
char* llist1_count_str = readline();
int llist1_count = strtol(llist1_count_str, &llist1_count_endptr, 10);
if (llist1_count_endptr == llist1_count_str || *llist1_count_endptr != '') { exit(EXIT_FAILURE); }
for (int i = 0; i < llist1_count; i++) {
char* llist1_item_endptr;
char* llist1_item_str = readline();
int llist1_item = strtol(llist1_item_str, &llist1_item_endptr, 10);
if (llist1_item_endptr == llist1_item_str || *llist1_item_endptr != '') { exit(EXIT_FAILURE); }
insert_node_into_singly_linked_list(&llist1, llist1_item);
}
SinglyLinkedList* llist2 = malloc(sizeof(SinglyLinkedList));
llist2->head = NULL;
llist2->tail = NULL;
char* llist2_count_endptr;
char* llist2_count_str = readline();
int llist2_count = strtol(llist2_count_str, &llist2_count_endptr, 10);
if (llist2_count_endptr == llist2_count_str || *llist2_count_endptr != '') { exit(EXIT_FAILURE); }
for (int i = 0; i < llist2_count; i++) {
char* llist2_item_endptr;
char* llist2_item_str = readline();
int llist2_item = strtol(llist2_item_str, &llist2_item_endptr, 10);
if (llist2_item_endptr == llist2_item_str || *llist2_item_endptr != '') { exit(EXIT_FAILURE); }
insert_node_into_singly_linked_list(&llist2, llist2_item);
}
SinglyLinkedListNode* ptr1 = llist1->head;
SinglyLinkedListNode* ptr2 = llist2->head;
for (int i = 0; i < llist1_count; i++) {
if (i < index) {
ptr1 = ptr1->next;
}
}
for (int i = 0; i < llist2_count; i++) {
if (i != llist2_count-1) {
ptr2 = ptr2->next;
}
}
ptr2->next = ptr1;
int result = findMergeNode(llist1->head, llist2->head);
fprintf(fptr, "%dn", result);
}
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == 'n') {
data[data_length - 1] = '';
}
data = realloc(data, data_length);
return data;
}
Problem solution in JavaScript programming.
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/s*$/, '')
.split('n')
.map(str => str.replace(/s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
const SinglyLinkedListNode = class {
constructor(nodeData) {
this.data = nodeData;
this.next = null;
}
};
const SinglyLinkedList = class {
constructor() {
this.head = null;
this.tail = null;
}
insertNode(nodeData) {
const node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
};
function printSinglyLinkedList(node, sep, ws) {
while (node != null) {
ws.write(String(node.data));
node = node.next;
if (node != null) {
ws.write(sep);
}
}
}
/*
Find merge point of two linked lists
Note that the head may be 'null' for the empty list.
Node is defined as
var Node = function(data) {
this.data = data;
this.next = null;
}
*/
// This is a "method-only" submission.
// You only need to complete this method.
function findMergeNode(a, b) {
let arr = [];
while (a || b) {
if (a && arr.find(n => n === a)) return a.data;
else if(a) {
arr.push(a)
a = a.next;
}
if (b && arr.find(n => n === b)) return b.data;
else if (b) {
arr.push(b);
b = b.next;
}
}
return 0;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const tests = parseInt(readLine(), 10);
for (let testsItr = 0; testsItr < tests; testsItr++) {
const index = parseInt(readLine(), 10);
const llist1Count = parseInt(readLine(), 10);
let llist1 = new SinglyLinkedList();
for (let i = 0; i < llist1Count; i++) {
const llist1Item = parseInt(readLine(), 10);
llist1.insertNode(llist1Item);
}
const llist2Count = parseInt(readLine(), 10);
let llist2 = new SinglyLinkedList();
for (let i = 0; i < llist2Count; i++) {
const llist2Item = parseInt(readLine(), 10);
llist2.insertNode(llist2Item);
}
let ptr1 = llist1.head;
let ptr2 = llist2.head;
for (let i = 0; i < llist1Count; i++) {
if (i < index) {
ptr1 = ptr1.next;
}
}
for (let i = 0; i < llist2Count; i++) {
if (i != llist2Count-1) {
ptr2 = ptr2.next;
}
}
ptr2.next = ptr1;
let result = findMergeNode(llist1.head, llist2.head);
ws.write(result + "n");
}
ws.end();
}