algorithm - ordenar - mezclar dos listas ordenadas

Entrevista: fusionar dos listas enlazadas individuales ordenadas

Question

Esta es una pregunta de programación realizada durante una prueba escrita para una entrevista. "Tienes dos listas unidas individualmente que ya están ordenadas, debes fusionarlas y devolver el encabezado de la nueva lista sin crear nuevos nodos adicionales. La lista devuelta debería ordenarse también"

La firma del método es: Node MergeLists (Node list1, Node list2);

La clase de nodo está debajo:

class Node{
int data;
Node next;
}

Intenté muchas soluciones, pero no crear un nodo adicional atornilla cosas. Por favor ayuda.

Aquí está la entrada del blog que lo acompaña http://techieme.in/merging-two-sorted-singly-linked-list/

Answer 1

¡Mira, no, recursión!

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;
for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
if (cmp(one,two) <=0) { *tail = one; one=one->next; }
else { *tail = two; two=two->next; }
}
*tail = one ? one: two;
return result;
}

Answer 2

¿Por qué todas estas soluciones son tan complicadas? No desea utilizar la recursión aquí porque podría recurrir demasiado profundamente y lanzar una excepción de desbordamiento de pila. Cada solución usa demasiadas líneas de código o usa recursión. Esta es una implementación Java extremadamente simple con declaraciones e inicializaciones ya incluidas.

 LinkedList<Integer> list1 = new LinkedList<Integer>();
LinkedList<Integer> list2 = new LinkedList<Integer>();
LinkedList<Integer> sortedList = new LinkedList<Integer>();
list1.add(1);
list1.add(3);
list1.add(5);
list1.add(7);
list1.add(9);
list2.add(2);
list2.add(4);
list2.add(6);
list2.add(8);
list2.add(10);
while (!list1.isEmpty() && !list2.isEmpty())
{
Integer first1 = list1.getFirst();
Integer first2 = list2.getFirst();
if(first1 < first2)
{
sortedList.add(first1);
list1.removeFirst();
}
else if(first2 > first1)
{
sortedList.add(first2);
list2.removeFirst();
}
else // if first1 == first2 then default to first1
{
sortedList.add(first1);
list1.removeFirst();
}
}
for (Integer i : list1) // add any remaining values from list1
sortedList.add(i);
for (Integer i : list2) // add any remaining values from list2
sortedList.add(i);
for (Integer i : sortedList) // print the sorted list
System.out.println(i);

Impresiones: 1 2 3 4 5 6 7 8 9 10

Answer 3

Aquí está el algoritmo sobre cómo combinar dos listas clasificadas A y B:

while A not empty or B not empty:
if first element of A < first element of B:
remove first element from A
insert element into C
end if
else:
remove first element from B
insert element into C
end while

Aquí C será la lista de salida.

Answer 4

Aquí está el código sobre cómo fusionar dos listas enlazadas ordenadas headA y headB:

Node* MergeLists1(Node *headA, Node* headB)
{
Node *p = headA;
Node *q = headB;
Node *result = NULL;
Node *pp = NULL;
Node *qq = NULL;
Node *head = NULL;
int value1 = 0;
int value2 = 0;
if((headA == NULL) && (headB == NULL))
{
return NULL;
}
if(headA==NULL)
{
return headB;
}
else if(headB==NULL)
{
return headA;
}
else
{
while((p != NULL) || (q != NULL))
{
if((p != NULL) && (q != NULL))
{
int value1 = p->data;
int value2 = q->data;
if(value1 <= value2)
{
pp = p->next;
p->next = NULL;
if(result == NULL)
{
head = result = p;
}
else
{
result->next = p;
result = p;
}
p = pp;
}
else
{
qq = q->next;
q->next = NULL;
if(result == NULL)
{
head = result = q;
}
else
{
result->next = q;
result = q;
}
q = qq;
}
}
else
{
if(p != NULL)
{
pp = p->next;
p->next = NULL;
result->next = p;
result = p;
p = pp;
}
if(q != NULL)
{
qq = q->next;
q->next = NULL;
result->next = q;
result = q;
q = qq;
}
}
}
}
return head;
}

Answer 5

Aquí hay un ejemplo de trabajo completo que usa la lista enlazada implementada java.util. Puedes copiar y pegar el código siguiente dentro de un método main ().

 LinkedList<Integer> dList1 = new LinkedList<Integer>();
LinkedList<Integer> dList2 = new LinkedList<Integer>();
LinkedList<Integer> dListMerged = new LinkedList<Integer>();
dList1.addLast(1);
dList1.addLast(8);
dList1.addLast(12);
dList1.addLast(15);
dList1.addLast(85);
dList2.addLast(2);
dList2.addLast(3);
dList2.addLast(12);
dList2.addLast(24);
dList2.addLast(85);
dList2.addLast(185);
int i = 0;
int y = 0;
int dList1Size = dList1.size();
int dList2Size = dList2.size();
int list1Item = dList1.get(i);
int list2Item = dList2.get(y);
while (i < dList1Size || y < dList2Size) {
if (i < dList1Size) {
if (list1Item <= list2Item || y >= dList2Size) {
dListMerged.addLast(list1Item);
i++;
if (i < dList1Size) {
list1Item = dList1.get(i);
}
}
}
if (y < dList2Size) {
if (list2Item <= list1Item || i >= dList1Size) {
dListMerged.addLast(list2Item);
y++;
if (y < dList2Size) {
list2Item = dList2.get(y);
}
}
}
}
for(int x:dListMerged)
{
System.out.println(x);
}

Answer 6

En primer lugar, comprenda la media de "sin crear nuevos nodos adicionales" . Según tengo entendido, esto no significa que no pueda tener un puntero (s) que apunte a un nodo (s) existente.

No puede lograrlo sin hablar con los punteros a los nodos existentes, incluso si usa recursividad para lograr lo mismo, el sistema creará punteros para usted como pilas de llamadas. Es como decirle al sistema que agregue punteros que ha evitado en su código.

Función simple para lograr lo mismo con la toma de punteros adicionales :

typedef struct _LLNode{
int value;
struct _LLNode* next;
}LLNode;
LLNode* CombineSortedLists(LLNode* a,LLNode* b){
if(NULL == a){
return b;
}
if(NULL == b){
return a;
}
LLNode* root = NULL;
if(a->value < b->value){
root = a;
a = a->next;
}
else{
root = b;
b = b->next;
}
LLNode* curr = root;
while(1){
if(a->value < b->value){
curr->next = a;
curr = a;
a=a->next;
if(NULL == a){
curr->next = b;
break;
}
}
else{
curr->next = b;
curr = b;
b=b->next;
if(NULL == b){
curr->next = a;
break;
}
}
}
return root;
}

Answer 7

Esto podría hacerse sin crear el nodo adicional, con solo otra referencia de nodo pasando a los parámetros (Temp de nodo).

private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
if(nodeList1 == null) return nodeList2;
if(nodeList2 == null) return nodeList1;
if(nodeList1.data <= nodeList2.data){
temp = nodeList1;
temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);
}
else{
temp = nodeList2;
temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);
}
return temp;
}

Answer 8

La iteración se puede hacer de la siguiente manera. Complejidad = O (n)

public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) {
LLNode mergedNode ;
LLNode tempNode ;
if (nodeA == null) {
return nodeB;
}
if (nodeB == null) {
return nodeA;
}
if ( nodeA.getData() < nodeB.getData())
{
mergedNode = nodeA;
nodeA = nodeA.getNext();
}
else
{
mergedNode = nodeB;
nodeB = nodeB.getNext();
}
tempNode = mergedNode;
while (nodeA != null && nodeB != null)
{
if ( nodeA.getData() < nodeB.getData())
{
mergedNode.setNext(nodeA);
nodeA = nodeA.getNext();
}
else
{
mergedNode.setNext(nodeB);
nodeB = nodeB.getNext();
}
mergedNode = mergedNode.getNext();
}
if (nodeA != null)
{
mergedNode.setNext(nodeA);
}
if (nodeB != null)
{
mergedNode.setNext(nodeB);
}
return tempNode;
}

Answer 9

La recursión no debería ser necesaria para evitar asignar un nuevo nodo:

Node MergeLists(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
Node head;
if (list1.data < list2.data) {
head = list1;
} else {
head = list2;
list2 = list1;
list1 = head;
}
while(list1.next != null) {
if (list1.next.data > list2.data) {
Node tmp = list1.next;
list1.next = list2;
list2 = tmp;
}
list1 = list1.next;
}
list1.next = list2;
return head;
}

Answer 10

Me gustaría compartir cómo pensé que era la solución ... vi la solución que implica la recursión y son bastante sorprendentes, es el resultado de un pensamiento funcional y modular. Realmente aprecio el intercambio.

Me gustaría agregar que la recursión no funcionará para las grandes letras, las llamadas a la pila se desbordarán; así que decidí probar el enfoque iterativo ... y esto es lo que obtengo.

El código es bastante auto explicativo, agregué algunos comentarios en línea para tratar de asegurar esto.

Si no lo obtiene, notifíqueme y mejoraré la legibilidad (tal vez estoy interpretando erróneamente mi propio código).

import java.util.Random;
public class Solution {
public static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> {
T data;
Node next;
@Override
public int compareTo(Node<T> otherNode) {
return data.compareTo(otherNode.data);
}
@Override
public String toString() {
return ((data != null) ? data.toString() + ((next != null) ? "," + next.toString() : "") : "null");
}
}
public static Node merge(Node firstLeft, Node firstRight) {
combine(firstLeft, firstRight);
return Comparision.perform(firstLeft, firstRight).min;
}
private static void combine(Node leftNode, Node rightNode) {
while (leftNode != null && rightNode != null) {
// get comparision data about "current pair of nodes being analized".
Comparision comparision = Comparision.perform(leftNode, rightNode);
// stores references to the next nodes
Node nextLeft = leftNode.next;
Node nextRight = rightNode.next;
// set the "next node" of the "minor node" between the "current pair of nodes being analized"...
// ...to be equals the minor node between the "major node" and "the next one of the minor node" of the former comparision.
comparision.min.next = Comparision.perform(comparision.max, comparision.min.next).min;
if (comparision.min == leftNode) {
leftNode = nextLeft;
} else {
rightNode = nextRight;
}
}
}
/** Stores references to two nodes viewed as one minimum and one maximum. The static factory method populates properly the instance being build */
private static class Comparision {
private final Node min;
private final Node max;
private Comparision(Node min, Node max) {
this.min = min;
this.max = max;
}
private static Comparision perform(Node a, Node b) {
Node min, max;
if (a != null && b != null) {
int comparision = a.compareTo(b);
if (comparision <= 0) {
min = a;
max = b;
} else {
min = b;
max = a;
}
} else {
max = null;
min = (a != null) ? a : b;
}
return new Comparision(min, max);
}
}
// Test example....
public static void main(String args[]) {
Node firstLeft = buildList(20);
Node firstRight = buildList(40);
Node firstBoth = merge(firstLeft, firstRight);
System.out.println(firstBoth);
}
// someone need to write something like this i guess...
public static Node buildList(int size) {
Random r = new Random();
Node<Integer> first = new Node<>();
first.data = 0;
first.next = null;
Node<Integer> current = first;
Integer last = first.data;
for (int i = 1; i < size; i++) {
Node<Integer> node = new Node<>();
node.data = last + r.nextInt(5);
last = node.data;
node.next = null;
current.next = node;
current = node;
}
return first;
}

}

Answer 11

Mi opinión sobre la pregunta es la siguiente:

Pseudocódigo:

Compare the two heads A and B.
If A <= B, then add A and move the head of A to the next node.
Similarly, if B < A, then add B and move the head of B to the next node B.
If both A and B are NULL then stop and return.
If either of them is NULL, then traverse the non null head till it becomes NULL.

Código:

public Node mergeLists(Node headA, Node headB) {
Node merge = null;
// If we have reached the end, then stop.
while (headA != null || headB != null) {
// if B is null then keep appending A, else check if value of A is lesser or equal than B
if (headB == null || (headA != null && headA.data <= headB.data)) {
// Add the new node, handle addition separately in a new method.
merge = add(merge, headA.data);
// Since A is <= B, Move head of A to next node
headA = headA.next;
// if A is null then keep appending B, else check if value of B is lesser than A
} else if (headA == null || (headB != null && headB.data < headA.data)) {
// Add the new node, handle addition separately in a new method.
merge = add(merge, headB.data);
// Since B is < A, Move head of B to next node
headB = headB.next;
}
}
return merge;
}
public Node add(Node head, int data) {
Node end = new Node(data);
if (head == null) {
return end;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = end;
return head;
}

Answer 12

Una solución iterativa simple.

Nodo * MergeLists (Node * A, Node * B) {// manejo de los casos de esquina

//if both lists are empty
if(!A && !B)
{
cout << "List is empty" << endl;
return 0;
}
//either of list is empty
else if(!A) return B;
else if(!B) return A;
else
{
Node* head = NULL;//this will be the head of the newList
Node* previous = NULL;//this will act as the
/* In this algorithm we will keep the
previous pointer that will point to the last node of the output list.
And, as given we have A & B as pointer to the given lists.
The algorithm will keep on going untill either one of the list become empty.
Inside of the while loop, it will divide the algorithm in two parts:
- First, if the head of the output list is not obtained yet
- Second, if head is already there then we will just compare the values and keep appending to the ''previous'' pointer.
When one of the list become empty we will append the other ''left over'' list to the output list.
*/
while(A && B)
{
if(!head)
{
if(A->data <= B->data)
{
head = A;//setting head of the output list to A
previous = A; //initializing previous
A = A->next;
}
else
{
head = B;//setting head of the output list to B
previous = B;//initializing previous
B = B->next;
}
}
else//when head is already set
{
if(A->data <= B->data)
{
if(previous->next != A)
previous->next = A;
A = A->next;//Moved A forward but keeping B at the same position
}
else
{
if(previous->next != B)
previous->next = B;
B = B->next; //Moved B forward but keeping A at the same position
}
previous = previous->next;//Moving the Output list pointer forward
}
}
//at the end either one of the list would finish
//and we have to append the other list to the output list
if(!A)
previous->next = B;
if(!B)
previous->next = A;
return head; //returning the head of the output list
}

}

Answer 13

Manera recursiva (variante de la respuesta de Stefan)

 MergeList(Node nodeA, Node nodeB ){
if(nodeA==null){return nodeB};
if(nodeB==null){return nodeA};
if(nodeB.data<nodeA.data){
Node returnNode = MergeNode(nodeA,nodeB.next);
nodeB.next = returnNode;
retturn nodeB;
}else{
Node returnNode = MergeNode(nodeA.next,nodeB);
nodeA.next=returnNode;
return nodeA;
}

Considere la siguiente lista vinculada para visualizar esto

2>4 lista A 1>3 lista B

Casi la misma respuesta (no recursiva) que Stefan, pero con pocos comentarios más / nombre de variable significativo. También se incluye una doble lista de enlaces en los comentarios si alguien está interesado

Considera el ejemplo

5->10->15>21 // List1

2->3->6->20 //List2

Node MergeLists(List list1, List list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if(list1.head.data>list2.head.data){
listB =list2; // loop over this list as its head is smaller
listA =list1;
} else {
listA =list2; // loop over this list
listB =list1;
}
listB.currentNode=listB.head;
listA.currentNode=listA.head;
while(listB.currentNode!=null){
if(listB.currentNode.data<listA.currentNode.data){
Node insertFromNode = listB.currentNode.prev;
Node startingNode = listA.currentNode;
Node temp = inserFromNode.next;
inserFromNode.next = startingNode;
startingNode.next=temp;
startingNode.next.prev= startingNode; // for doubly linked list
startingNode.prev=inserFromNode; // for doubly linked list
listB.currentNode= listB.currentNode.next;
listA.currentNode= listA.currentNode.next;
}
else
{
listB.currentNode= listB.currentNode.next;
}
}

Answer 14

 /* Simple/Elegant Iterative approach in Java*/
private static LinkedList mergeLists(LinkedList list1, LinkedList list2) {
Node head1 = list1.start;
Node head2 = list2.start;
if (list1.size == 0)
return list2;
if (list2.size == 0)
return list1;
LinkedList mergeList = new LinkedList();
while (head1 != null && head2 != null) {
if (head1.getData() < head2.getData()) {
int data = head1.getData();
mergeList.insert(data);
head1 = head1.getNext();
} else {
int data = head2.getData();
mergeList.insert(data);
head2 = head2.getNext();
}
}
while (head1 != null) {
int data = head1.getData();
mergeList.insert(data);
head1 = head1.getNext();
}
while (head2 != null) {
int data = head2.getData();
mergeList.insert(data);
head2 = head2.getNext();
}
return mergeList;
}
/* Build-In singly LinkedList class in Java*/
class LinkedList {
Node start;
int size = 0;
void insert(int data) {
if (start == null)
start = new Node(data);
else {
Node temp = start;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(new Node(data));
}
size++;
}
@Override
public String toString() {
String str = "";
Node temp=start;
while (temp != null) {
str += temp.getData() + "-->";
temp = temp.getNext();
}
return str;
}
}

Answer 15

LLNode *mergeSorted(LLNode *h1, LLNode *h2)
{
LLNode *h3=NULL;
LLNode *h3l;
if(h1==NULL && h2==NULL)
return NULL;
if(h1==NULL)
return h2;
if(h2==NULL)
return h1;
if(h1->data<h2->data)
{
h3=h1;
h1=h1->next;
}
else
{
h3=h2;
h2=h2->next;
}
LLNode *oh=h3;
while(h1!=NULL && h2!=NULL)
{
if(h1->data<h2->data)
{
h3->next=h1;
h3=h3->next;
h1=h1->next;
}
else
{
h3->next=h2;
h3=h3->next;
h2=h2->next;
}
}
if(h1==NULL)
h3->next=h2;
if(h2==NULL)
h3->next=h1;
return oh;
}

Answer 16

Node * merge_sort(Node *a, Node *b){
Node *result = NULL;
if(a == NULL)
return b;
else if(b == NULL)
return a;
/* For the first node, we would set the result to either a or b */
if(a->data <= b->data){
result = a;
/* Result''s next will point to smaller one in lists
starting at a->next and b */
result->next = merge_sort(a->next,b);
}
else {
result = b;
/*Result''s next will point to smaller one in lists
starting at a and b->next */
result->next = merge_sort(a,b->next);
}
return result;
}

Por favor, consulte la publicación de mi blog para http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html

Answer 17

Node MergeLists(Node list1, Node list2) {
//if list is null return other list
if(list1 == null)
{
return list2;
}
else if(list2 == null)
{
return list1;
}
else
{
Node head;
//Take head pointer to the node which has smaller first data node
if(list1.data < list2.data)
{
head = list1;
list1 = list1.next;
}
else
{
head = list2;
list2 = list2.next;
}
Node current = head;
//loop till both list are not pointing to null
while(list1 != null || list2 != null)
{
//if list1 is null, point rest of list2 by current pointer
if(list1 == null){
current.next = list2;
return head;
}
//if list2 is null, point rest of list1 by current pointer
else if(list2 == null){
current.next = list1;
return head;
}
//compare if list1 node data is smaller than list2 node data, list1 node will be
//pointed by current pointer
else if(list1.data < list2.data)
{
current.next = list1;
current = current.next;
list1 = list1.next;
}
else
{
current.next = list2;
current = current.next;
list2 = list2.next;
}
}
return head;
}
}

Answer 18

Node MergeLists(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.data < list2.data) {
list1.next = MergeLists(list1.next, list2);
return list1;
} else {
list2.next = MergeLists(list2.next, list1);
return list2;
}
}

Answer 19

Node MergeLists(Node node1, Node node2)
{
if(node1 == null)
return node2;
else (node2 == null)
return node1;
Node head;
if(node1.data < node2.data)
{
head = node1;
node1 = node1.next;
else
{
head = node2;
node2 = node2.next;
}
Node current = head;
while((node1 != null) ||( node2 != null))
{
if (node1 == null) {
current.next = node2;
return head;
}
else if (node2 == null) {
current.next = node1;
return head;
}
if (node1.data < node2.data)
{
current.next = node1;
current = current.next;
node1 = node1.next;
}
else
{
current.next = node2;
current = current.next;
node2 = node2.next;
}
}
current.next = NULL // needed to complete the tail of the merged list
return head;
}

Answer 20

Node mergeList(Node h1, Node h2) {
if (h1 == null) return h2;
if (h2 == null) return h1;
Node head;
if (h1.data < h2.data) {
head = h1;
} else {
head = h2;
h2 = h1;
h1 = head;
}
while (h1.next != null && h2 != null) {
if (h1.next.data < h2.data) {
h1 = h1.next;
} else {
Node afterh2 = h2.next;
Node afterh1 = h1.next;
h1.next = h2;
h2.next = afterh1;
if (h2.next != null) {
h2 = afterh2;
}
}
}
return head;
}

Answer 21

private static Node mergeLists(Node L1, Node L2) {
Node P1 = L1.val < L2.val ? L1 : L2;
Node P2 = L1.val < L2.val ? L2 : L1;
Node BigListHead = P1;
Node tempNode = null;
while (P1 != null && P2 != null) {
if (P1.next != null && P1.next.val >P2.val) {
tempNode = P1.next;
P1.next = P2;
P1 = P2;
P2 = tempNode;
} else if(P1.next != null)
P1 = P1.next;
else {
P1.next = P2;
break;
}
}
return BigListHead;
}

Answer 22

public static Node merge(Node h1, Node h2) {
Node h3 = new Node(0);
Node current = h3;
boolean isH1Left = false;
boolean isH2Left = false;
while (h1 != null || h2 != null) {
if (h1.data <= h2.data) {
current.next = h1;
h1 = h1.next;
} else {
current.next = h2;
h2 = h2.next;
}
current = current.next;
if (h2 == null && h1 != null) {
isH1Left = true;
break;
}
if (h1 == null && h2 != null) {
isH2Left = true;
break;
}
}
if (isH1Left) {
while (h1 != null) {
current.next = h1;
current = current.next;
h1 = h1.next;
}
}
if (isH2Left) {
while (h2 != null) {
current.next = h2;
current = current.next;
h2 = h2.next;
}
}
h3 = h3.next;
return h3;
}

Answer 23

void printLL(){
NodeLL cur = head;
if(cur.getNext() == null){
System.out.println("LL is emplty");
}else{
//System.out.println("printing Node");
while(cur.getNext() != null){
cur = cur.getNext();
System.out.print(cur.getData()+ " ");
}
}
System.out.println();
}
void mergeSortedList(NodeLL node1, NodeLL node2){
NodeLL cur1 = node1.getNext();
NodeLL cur2 = node2.getNext();
NodeLL cur = head;
if(cur1 == null){
cur = node2;
}
if(cur2 == null){
cur = node1;
}
while(cur1 != null && cur2 != null){
if(cur1.getData() <= cur2.getData()){
cur.setNext(cur1);
cur1 = cur1.getNext();
}
else{
cur.setNext(cur2);
cur2 = cur2.getNext();
}
cur = cur.getNext();
}
while(cur1 != null){
cur.setNext(cur1);
cur1 = cur1.getNext();
cur = cur.getNext();
}
while(cur2 != null){
cur.setNext(cur2);
cur2 = cur2.getNext();
cur = cur.getNext();
}
printLL();
}