Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
O(a + b)
private static ListNode merge(ListNode a, ListNode b) {
ListNode result = null;
ListNode head = null;
while (a != null && b != null) {
ListNode newNode;
if (a.data < b.data) {
newNode = new ListNode(a.data);
a = a.next;
} else {
newNode = new ListNode(b.data);
b = b.next;
}
if (head == null) {
head = result = newNode;
} else {
result.next = newNode;
result = result.next;
}
}
while (a != null) {
ListNode newNode = new ListNode(a.data);
a = a.next;
if (head == null) {
head = result = newNode;
} else {
result.next = newNode;
result = result.next;
}
}
while (b != null) {
ListNode newNode = new ListNode(b.data);
b = b.next;
if (head == null) {
head = result = newNode;
} else {
result.next = newNode;
result = result.next;
}
}
return head;
}
private static class ListNode {
int data;
ListNode next;
private ListNode(int data) {
this.data = data;
}
}
Classically merge of values, but with tracking of the tail of the merged list (so that one can do "append to the end" in constant time).
complexity: O(1) space
time: O(N+M) = O(N) with N>=M
list 1 is length N
list 2 is length M
Here's some python that does this:
def merge(left, right):
if left.data < right.data:
head = left
left = left.node
else:
head = right
right = right.node
tail = head
while left or right:
if left and right:
if left.data < right.data:
tail.node = left
left = left.node
else:
tail.node = right
right = right.node
elif left:
tail.node = left
left = left.node
else:
tail.node = right
right = right.node
tail = tail.node
return head
This is with a single while but it is too complicated because I need one pointer to the head and one to the current element. I prefer mergeTwoSortedLinkList with recursion. It is more elegant.
public LinkedList merger(LinkedList l1, LinkedList l2){
LinkedList tmp = null;
LinkedList result = null;
while(true) {
if (l1 == null && l2 == null) break;
if (l2 == null || (l1 != null && l1.value <= l2.value)) {
if (tmp == null) {
tmp = l1;
result = tmp;
}
else {
tmp.setNext(l1);
tmp = tmp.next();
}
l1 = l1.next();
}
else if (l1 == null || (l2 != null && l1.value > l2.value)) {
if (tmp == null) {
tmp = l2;
result = tmp;
}
else {
tmp.setNext(l2);
tmp = tmp.next();
}
l2 = l2.next();
}
}
return result;
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode newHead = new ListNode(0);
ListNode pre = newHead;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
pre.next = l1;
l1 = l1.next;
} else{
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
if(l1!= null)
pre.next = l1;
if(l2!= null)
pre.next = l2;
return newHead.next;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
namespace ConsoleApplication1
{
class ListNode
{
public int val;
public ListNode Next = null;
}
class LinkSortedLists
{
ListNode start1 = null, start2 = null;
public LinkSortedLists()
{
int n = 0;
ListNode third,temp;
Console.WriteLine("Enter the number of elements in list one");
n = Int32.Parse(Console.ReadLine());
PrepareList(ref start1,n);
n = 0;
Console.WriteLine("Enter the number of elements in list Two");
n = Int32.Parse(Console.ReadLine());
PrepareList(ref start2, n);
third = MergeTwoSortedList(start1, start2);
if (third != null)
{
temp = third;
Console.WriteLine("Sorted List is As: ");
while (temp != null)
{
Console.WriteLine(temp.val);
temp = temp.Next;
}
}
else
{
Console.WriteLine("No element in the linked list");
}
}
public void PrepareList(ref ListNode start,int elementCount)
{
if (elementCount > 0)
{
Console.WriteLine("Enter " + elementCount + " values in the list");
ListNode temp = null;
for (int i = 0; i < elementCount; i++)
{
if (i == 0)
{
start = new ListNode();
start.val = Int32.Parse(Console.ReadLine());
temp = start;
}
else
{
int val = Int32.Parse(Console.ReadLine());
if (val >= temp.val)
{
temp.Next = new ListNode();
temp = temp.Next;
temp.val = val;
}
else
{
Console.WriteLine("Not a sorted list ");
Thread.Sleep(500);
Environment.Exit(0);
}
}
}
}
}
public ListNode MergeTwoSortedList(ListNode first, ListNode second )
{
ListNode Third = null;
ListNode lastAdded = null;
while (first!= null && second != null)
{
if (first.val <= second.val)
{
if (Third == null)
{
Third = first;
lastAdded = first;
}
else
{
lastAdded.Next = first;
lastAdded = first;
}
first= first.Next;
}
else
{
if (Third == null)
{
Third = second ;
lastAdded = second;
}
else
{
lastAdded.Next = second ;
lastAdded = second ;
}
second = second.Next;
}
}
if (first == null)
{
while (second != null)
{
if (Third == null)
{
Third = second;
lastAdded = second;
}
else
{
lastAdded.Next = second;
lastAdded = second;
}
second = second.Next;
}
}
if (second == null)
{
while (first != null)
{
if (Third == null)
{
Third = first;
lastAdded = first;
}
else
{
lastAdded.Next = first;
lastAdded = first;
}
first = first.Next;
}
}
return Third;
}
}
}
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
struct Node*next;
};
void insert_data(int,struct Node**);
void show_data(struct Node**);
void add_in_sorted(struct Node**,struct Node**);
main()
{
struct Node*root1=NULL,*root2=NULL;
int value;
char check;
printf("\nInsert Element on First Lineked List\n");
do
{
printf("\nEnter data:- ");
scanf("%d",&value);
fflush(stdin);
insert_data(value,&root1);
printf("\n Enter another data(y/n):-");
scanf("%c",&check);
}while(check=='y'||check=='Y');
printf("\nInsert Element on 2nd Lineked List\n");
do
{
printf("\nEnter data:- ");
scanf("%d",&value);
fflush(stdin);
insert_data(value,&root2);
printf("\n Enter another data(y/n):-");
scanf("%c",&check);
}while(check=='y'||check=='Y');
printf("\n First Linked\n");
show_data(&root1);
printf("\n Second Linked");
show_data(&root2);
printf("\n combine in sorted order\n");
add_in_sorted(&root1,&root2);
show_data(&root1);
}
void insert_data(int value,struct Node**temp){
struct Node*t1,*newData=(struct Node*)malloc(sizeof(struct Node));
if(newData)
{
newData->data=value;
newData->next=NULL;
if(*temp==NULL)
{
*temp=newData;
}
else
{
t1=*temp;
while(t1->next!=NULL)
t1=t1->next;
t1->next=newData;
}
}
else
printf("\nMemory Problem");
}
void show_data(struct Node**temp){
if(*temp==NULL)
printf("no element in this List");
else
{
struct Node*t1=*temp;
printf("\n");
while(t1!=NULL)
{
printf("%5d",t1->data);
t1=t1->next;
}
}
}
void add_in_sorted(struct Node**temp1,struct Node**temp2)
{
if(*temp1&&*temp2)
{
struct Node*t1,*t2,*t3;
t1=*temp1;
t2=*temp2;
t3=*temp1;
if((t1->data)>t2->data)
{
t1=*temp2;
t2=*temp1;
t3=*temp2;
}
*temp1=t3;
while(t1!=NULL&&t2!=NULL)
{
if(t1->next!=NULL&&t1->next->data>t2->data)
{
t3=t1->next;
t1->next=t2;
t2=t3;
t1=t1->next;
}
else
{
if(t1->next==NULL)
{
t1->next=t2;
break;
}
else
t1=t1->next;
}
}
}
else
{
printf("\n Linked List is Null");
}
}
package com.engineeringkida.puzzle;
/*
* Given two sorted linked lists of integers
* write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order.
* You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.
*
*/
public class Problem6 {
public void addElement(){
System.out.println("---------------------list 1-------------------");
Node start=null;
start=addElement(start,1);
start=addElement(start,11);
start=addElement(start,3);
start=addElement(start,22);
start=addElement(start,6);
start=addElement(start,35);
start=addElement(start,24);
printelment(start);
System.out.println("---------------------list 2-------------------");
Node start1=null;
start1=addElement(start1,11);
start1=addElement(start1,12);
start1=addElement(start1,4);
start1=addElement(start1,7);
start1=addElement(start1,2);
start1=addElement(start1,15);
start1=addElement(start1,14);
printelment(start1);
System.out.println("--------------------list1 + list2 --------------------");
meargeList(start, start1);
}
public Node addElement(Node start, int data){
if(start==null){
start=new Node(data);
}
else if(data < start.getData()){
Node node=new Node(data);
node.setNext(start);
start=node;
}
else {
Node current=start;
Node prev=null;
while(current!=null){
if(current.getData() < data){
prev=current;
current=current.getNext();
}
else if(current.getData() > data && prev.getData() < data){
Node tmp=new Node(data);
tmp.setNext(current);
prev.setNext(tmp);
break;
}
else if(current.getData()==data){
Node tmp=new Node(data);
tmp.setNext(current.getNext());
current.setNext(tmp);
break;
}
}
if(current==null){
prev.setNext(new Node(data));
}
}
return start;
}
public void printelment(Node start){
Node current=start;
while(current!=null){
System.out.println(current.getData());
current=current.getNext();
}
}
public void meargeList(Node list1,Node list2){
Node current=list2;
while(current!=null){
list1=addElement(list1, current.getData());
current=current.getNext();
}
printelment(list1);
}
class Node {
int data;
Node next;
Node(int data) {
this.setData(data);
this.setNext(null);
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public static void main(String ar[]){
Problem6 problem6=new Problem6();
problem6.addElement();
}
}
Hello, guys! I was practiced a little bit and this is my answer. Let me know if I am wrong with this, I'd appreciate it
private static int countRepeated = 0;
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
int[] array2 = {3, 4, 5, 1};
System.out.print(Arrays.toString(mergedArrays(array, array2)));
}
public static int[] mergedArrays(int[] firstArray, int[] secondArray){
int[] mergeArray = new int[(firstArray.length + secondArray.length)];
int i = 0;
int j = 0;
int k = 0;
while( i < firstArray.length && j < secondArray.length){
if(firstArray[i] < secondArray[j]){
if(isRepeated(mergeArray, firstArray[i]))
mergeArray[k++] = firstArray[i];
i++;
}else{
if(isRepeated(mergeArray, secondArray[j]))
mergeArray[k++] = secondArray[j];
j++;
}
while(i < firstArray.length){
if(isRepeated(mergeArray, firstArray[i]))
mergeArray[k++] = firstArray[i];
i++;
}
while (j < secondArray.length){
if(isRepeated(mergeArray, secondArray[j]))
mergeArray[k++] = secondArray[j];
j++;
}
}
return bubbleSort(mergeArray, mergeArray.length);
}
public static boolean isRepeated(int[] mergeArray, int number) {
boolean repeated = true;
for(int i = 0; i < mergeArray.length; i ++){
if(mergeArray[i] == number){
countRepeated++;
repeated = false;
break;
}
}
return repeated;
}
private static int[] bubbleSort(int[] array, int size) {
if(size == 1){
int[] arrayCleaned = new int[array.length - countRepeated];
for(int i = 0; i < array.length; i++){
if(array[i] != 0)
arrayCleaned[i] = array[i];
}
return arrayCleaned;
}
int current;
for(int i = 0; i < size - 1; i ++){
if(array[i] < array[i + 1]){
current = array[i];
array[i] = array[i + 1];
array[i + 1] = current;
}
}
return bubbleSort(array, size - 1);
}
Hello, guys! I was practiced a little bit and this is my answer. Let me know if I am wrong with this, I'd appreciate it
private static int countRepeated = 0;
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
int[] array2 = {3, 4, 5, 1};
System.out.print(Arrays.toString(mergedArrays(array, array2)));
}
public static int[] mergedArrays(int[] firstArray, int[] secondArray){
int[] mergeArray = new int[(firstArray.length + secondArray.length)];
int i = 0;
int j = 0;
int k = 0;
while( i < firstArray.length && j < secondArray.length){
if(firstArray[i] < secondArray[j]){
if(isRepeated(mergeArray, firstArray[i]))
mergeArray[k++] = firstArray[i];
i++;
}else{
if(isRepeated(mergeArray, secondArray[j]))
mergeArray[k++] = secondArray[j];
j++;
}
while(i < firstArray.length){
if(isRepeated(mergeArray, firstArray[i]))
mergeArray[k++] = firstArray[i];
i++;
}
while (j < secondArray.length){
if(isRepeated(mergeArray, secondArray[j]))
mergeArray[k++] = secondArray[j];
j++;
}
}
return bubbleSort(mergeArray, mergeArray.length);
}
public static boolean isRepeated(int[] mergeArray, int number) {
boolean repeated = true;
for(int i = 0; i < mergeArray.length; i ++){
if(mergeArray[i] == number){
countRepeated++;
repeated = false;
break;
}
}
return repeated;
}
private static int[] bubbleSort(int[] array, int size) {
if(size == 1){
int[] arrayCleaned = new int[array.length - countRepeated];
for(int i = 0; i < array.length; i++){
if(array[i] != 0)
arrayCleaned[i] = array[i];
}
return arrayCleaned;
}
int current;
for(int i = 0; i < size - 1; i ++){
if(array[i] < array[i + 1]){
current = array[i];
array[i] = array[i + 1];
array[i + 1] = current;
}
}
return bubbleSort(array, size - 1);
}
class Element:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self, values):
self.root = Element(values[0])
last = self.root
for v in values[1:]:
last.next = Element(v)
last = last.next
def __str__(self):
e = self.root
l = list()
while e:
l.append(e.val)
e = e.next
return str(l)
def join_sorted(self, other):
e1 = self.root
e2 = other.root
r = list()
while e1 and e2:
if e1.val < e2.val:
r.append(e1.val)
e1 = e1.next
else:
r.append(e2.val)
e2 = e2.next
while e1:
r.append(e1.val)
e1 = e1.next
while e2:
r.append(e2.val)
e2 = e2.next
return LinkedList(r)
l1 = LinkedList([1, 3, 5, 7, 9, 15, 15])
l2 = LinkedList([2, 4, 6, 8, 9, 10, 11, 12])
l3 = l1.join_sorted(l2)
print(l1)
print(l2)
print(l3)
runtime O(NM) where N is size of first linked list and M is size of second linked list
SpaceComplexity(1)
public class MergeSortedLinkedList {
public static class Node {
int a;
Node next;
}
public Node mergeSortedLinkedList(Node n1, Node n2) {
Node head = n1;
Node n = n2;
while(n!=null) {
Node prev = null;
Node cur = head;
while (cur != null) {
if(n.a <= cur.a) {
Node nextN = n.next;
n.next = cur;
if(prev != null) {
prev.next = n;
} else {
head = n;
}
n = nextN;
break;
}
prev = cur;
cur = cur.next;
if(cur == null) {
Node nextN = n.next;
prev.next = n;
n = nextN;
}
}
}
return head;
}
public static void main(String[] args) {
Node head = new Node();
Node two = new Node();
Node three = new Node();
head.a = 20; head.next = two;
two.a = 53; two.next = three;
three.a = 95; three.next = null;
Node head2 = new Node();
Node two2 = new Node();
Node three2 = new Node();
head2.a = 15; head2.next = two2;
two2.a = 30; two2.next = three2;
three2.a = 95; three2.next = null;
Node merged = new MergeSortedLinkedList().mergeSortedLinkedList(head, head2);
while(merged != null) {
System.out.print(merged.a + " -> ");
merged = merged.next;
}
}
}
C Program
/*
* Given two sorted linked lists of integers write an algorithm to merge the two linked lists
* such that the resulting linked list is in sorted order.
* You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.
*/
node_t *
mergeList (node_t *l1, node_t *l2)
{
node_t *l3 = NULL;
node_t *tl3 = NULL;
if (!l1 && !l2)
return l3; // Empty Lists
if (!l1)
return l2; // L1 is empty
if (!l2)
return l1; // L2 is empty
if (l1->data < l2->data) { // Findour head of merged list L3
tl3 = l1;
l1 = l1->nxt;
} else {
tl3 = l2;
l2 = l2->nxt;
}
l3 = tl3; // preserve head pointer tL3,
while (l1 && l2) {
if (l1->data < l2->data) {
l3->nxt = l1;
l1 = l1->nxt;
} else if (l1->data > l2->data) {
l3->nxt = l2;
l2 = l2->nxt;
} else {
l3 = l1;
l1 = l1->nxt;
l3 = l3->nxt;
l3 = l2;
l2 = l2->nxt;
}
l3 = l3->nxt;
}
if (l1) {
l3->nxt = l1;
} else {
l3->nxt = l2;
}
return tl3;
}
int main ()
{
node_t *listA = NULL;
node_t *listB = NULL;
node_t *listC = NULL;
insert(&listA, 7);
insert(&listA, 5);
insert(&listA, 3);
insert(&listA, 1);
insert(&listB, 8);
insert(&listB, 6);
insert(&listB, 4);
insert(&listB, 2);
print(listA);
print(listB);
listC = mergeList(listA, listB);
print(listC);
return 0;
}
output:
1 3 5 7
2 4 6 8
1 2 3 4 5 6 7 8
public class MergeAndSortTwoCustomList {
public ListNode resultList;
public void merge(ListNode l1, ListNode l2){
resultList = new ListNode();
mergeAndSort(0,0,l1,l2);
}
//Complex Time O(l1+l2) Complex Space O(l1+l2)
private void mergeAndSort(int index1, int index2, ListNode list1, ListNode list2) {
if(resultList.size() == (list1.size() + list2.size()))
return;
else if(index1 == list1.size()){
resultList.add(list2.get(index2++));
}else if(index2 == list2.size()){
resultList.add(list1.get(index1++));
}else if((list1.get(index1) < list2.get(index2))){
resultList.add(list1.get(index1++));
}else {
resultList.add(list2.get(index2++));
}
mergeAndSort(index1, index2, list1, list2);
}
static class ListNode {
private int size;
private Node head;
private Node tail;
void add(int value) {
if (head == null) {
head = new Node(value);
tail = head;
} else {
tail.next = new Node(value);
tail = tail.next;
}
size++;
}
int get(int index) {
Node node = head;
if (index != 0) {
for (int i = 1; i <= index; i++) {
node = node.next;
}
}
return node.value;
}
int size() {
return size;
}
public String toString(){
return "[" + asString(head) + "]";
}
private String asString(Node node) {
if(node == null)
return "";
return node.value + "," + asString(node.next);
}
private class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
}
public static void main(String arg[]){
MergeAndSortTwoCustomList mergeAndTwoSortedLists = new MergeAndSortTwoCustomList();
int a1[] = {1,4,6,7};
int a2[] = {2,5,50,60};
ListNode list1 = new ListNode();
for(int i=0; i < a1.length; i++)
list1.add(a1[i]);
ListNode list2 = new ListNode();
for(int i=0; i < a2.length; i++)
list2.add(a2[i]);
mergeAndTwoSortedLists.merge(list1,list2);
System.out.println(mergeAndTwoSortedLists.resultList.toString());
}
}
Time - O(N)
Space -O(N)
public static LinkedList<Integer> mergeLinkedList(LinkedList<Integer> left, LinkedList<Integer> right) {
LinkedList<Integer> mergedResult = new LinkedList<Integer>();
while(left.size() > 0 && right.size() > 0) {
if (left.getFirst() < right.getFirst()) {
mergedResult.add(left.remove());
} else {
mergedResult.add(right.remove());
}
}
if (left.size() > 0) {
mergedResult.addAll(left);
}
if (right.size() > 0) {
mergedResult.addAll(right);
}
return mergedResult;
}
Node MergeLists(Node headA, Node headB) {
// This is a "method-only" submission.
// You only need to complete this method
Node result = null;
if (headA == null) {
return headB;
} else if (headB == null){
return headA;
}
if (headA.data < headB.data){
result = headA;
result.next = MergeLists(headA.next, headB);
} else {
result = headB;
result.next = MergeLists(headB.next, headA);
}
return result;
}
public static LinkedList mergeList(LinkedList l1, LinkedList l2){
if(l1 == null || l2 == null) return null;
LinkedList l = new LinkedList();
int c=0;
for(int i=0;i<l1.size();i++){
if(c<l2.size()) {
if((int) l1.get(i) < (int) l2.get(c)){
l.add(l1.get(i));
}else {
l.add(l2.get(c));
c++;
i--;
}
}else l.add(l1.get(i));
}
return l;
}
static class IntNode {
public int Value;
public IntNode Next;
public IntNode(){ Value = 0; Next = null; }
public IntNode(int value) {
Value = value;
Next = null;
}
}
static class mergeIntNodesContext {
private final int N1 = 0, N2 = 1;
private IntNode[] nodes;
public mergeIntNodesContext(IntNode l1, IntNode l2) {
nodes = new IntNode[2];
nodes[N1] = l1;
nodes[N2] = l2;
}
public IntNode selectNext() {
if (nodes[N1] == null && nodes[N2] == null) return null;
if (nodes[N1] == null) return select(N2);
if (nodes[N2] == null) return select(N1);
if (nodes[N1].Value < nodes[N2].Value) return select(N1);
return select(N2);
}
private IntNode select(int index) {
IntNode selected = nodes[index];
nodes[index] = nodes[index].Next;
return selected;
}
}
private static IntNode mergeIntNodes(IntNode l1, IntNode l2) {
mergeIntNodesContext context = new mergeIntNodesContext(l1, l2);
IntNode merged = context.selectNext(), tail = merged;
while (tail != null)
tail = tail.Next = context.selectNext();
return merged;
}
while (iter1.hasNext()){
temp1 = (Integer)iter1.next();
iter2 = list2.listIterator();
while(iter2.hasNext()){
temp2 = (Integer)iter2.next();
if (temp1 > temp2){
finalList.add(temp2);
iter2.remove();
}
else{
finalList.add(temp1);
iter1.remove();
break;
}
}
}
if (list1.size() > 0){
finalList.add(list1.listIterator().next());
}
if (list2.size() > 0){
finalList.add(list2.listIterator().next());
}
while (iter1.hasNext()){
temp1 = (Integer)iter1.next();
iter2 = list2.listIterator();
while(iter2.hasNext()){
temp2 = (Integer)iter2.next();
if (temp1 > temp2){
finalList.add(temp2);
iter2.remove();
}
else{
finalList.add(temp1);
iter1.remove();
break;
}
}
}
if (list1.size() > 0){
finalList.add(list1.listIterator().next());
}
if (list2.size() > 0){
finalList.add(list2.listIterator().next());
}
while (iter1.hasNext()){
temp1 = (Integer)iter1.next();
iter2 = list2.listIterator();
while(iter2.hasNext()){
temp2 = (Integer)iter2.next();
if (temp1 > temp2){
finalList.add(temp2);
iter2.remove();
}
else{
finalList.add(temp1);
iter1.remove();
break;
}
}
}
if (list1.size() > 0){
finalList.add(list1.listIterator().next());
}
if (list2.size() > 0){
finalList.add(list2.listIterator().next());
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
namespace ConsoleApplication1
{
class ListNode
{
public int val;
public ListNode Next = null;
}
class LinkSortedLists
{
ListNode start1 = null, start2 = null;
public LinkSortedLists()
{
int n = 0;
ListNode third,temp;
Console.WriteLine("Enter the number of elements in list one");
n = Int32.Parse(Console.ReadLine());
PrepareList(ref start1,n);
n = 0;
Console.WriteLine("Enter the number of elements in list Two");
n = Int32.Parse(Console.ReadLine());
PrepareList(ref start2, n);
third = MergeTwoSortedList(start1, start2);
if (third != null)
{
temp = third;
Console.WriteLine("Sorted List is As: ");
while (temp != null)
{
Console.WriteLine(temp.val);
temp = temp.Next;
}
}
else
{
Console.WriteLine("No element in the linked list");
}
}
public void PrepareList(ref ListNode start,int elementCount)
{
if (elementCount > 0)
{
Console.WriteLine("Enter " + elementCount + " values in the list");
ListNode temp = null;
for (int i = 0; i < elementCount; i++)
{
if (i == 0)
{
start = new ListNode();
start.val = Int32.Parse(Console.ReadLine());
temp = start;
}
else
{
int val = Int32.Parse(Console.ReadLine());
if (val >= temp.val)
{
temp.Next = new ListNode();
temp = temp.Next;
temp.val = val;
}
else
{
Console.WriteLine("Not a sorted list ");
Thread.Sleep(500);
Environment.Exit(0);
}
}
}
}
}
public ListNode MergeTwoSortedList(ListNode first, ListNode second )
{
ListNode Third = null;
ListNode lastAdded = null;
while (first!= null && second != null)
{
if (first.val <= second.val)
{
if (Third == null)
{
Third = first;
lastAdded = first;
}
else
{
lastAdded.Next = first;
lastAdded = first;
}
first= first.Next;
}
else
{
if (Third == null)
{
Third = second ;
lastAdded = second;
}
else
{
lastAdded.Next = second ;
lastAdded = second ;
}
second = second.Next;
}
}
if (first == null)
{
while (second != null)
{
if (Third == null)
{
Third = second;
lastAdded = second;
}
else
{
lastAdded.Next = second;
lastAdded = second;
}
second = second.Next;
}
}
if (second == null)
{
while (first != null)
{
if (Third == null)
{
Third = first;
lastAdded = first;
}
else
{
lastAdded.Next = first;
lastAdded = first;
}
first = first.Next;
}
}
return Third;
}
}
}
- verma82 April 29, 2016public ListNode mergeTwoSortedLinkList(ListNode firstList, ListNode secondList) { ListNode finalList = null; if (finalList == null && secondList == null) { return finalList; } else if (firstList == null) { return secondList; } else if (secondList == null) { return firstList; } else { if (firstList.getData() <= secondList.getData()) { finalList = firstList; finalList.setNextNode(mergeTwoSortedLinkList(firstList.getNextNode(), secondList)); } else { finalList = secondList; finalList.setNextNode(mergeTwoSortedLinkList(firstList, secondList.getNextNode())); } } return finalList; }