Интервью: Объединение двух отсортированных односвязных списков

Это вопрос программирования, заданный во время письменного теста для собеседования. «У вас есть два отдельно связанных списка, которые уже отсортированы, вы должны объединить их и вернуть главу нового списка без создания каких-либо новых дополнительных узлов. Возвращенный список также должен быть отсортирован»,

Подпись метода: Node MergeLists (Node list1, Node list2);

Класс узла ниже:

class Node{ int data; Node next; } 

Я пробовал много решений, но не создавал лишние винты. Пожалуйста помоги.

Вот сопроводительная запись в блоге http://techieme.in/merging-two-sorted-singly-linked-list/

 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; } } 

Рекурсия не требуется, чтобы избежать выделения нового узла:

 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; } 
 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; } 

Вот алгоритм о том, как объединить два отсортированных связанных списка A и 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 

Здесь C будет выходным списком.

Смотри ма, нет рекурсии!

 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; } 

Итерацию можно выполнить, как показано ниже. Сложность = 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; } А 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; } А 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; } 
 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; } 

Простое итеративное решение.

Узел * MergeLists (Node * A, Node * B) {// обработка угловых случаев

 //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 } 

}

Это можно было бы сделать, не создавая дополнительный узел, только с другой ссылкой на Node, передающей параметры (Node temp).

 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; } 

Я хотел бы поделиться тем, как я думал о решении … Я видел решение, которое включает в себя рекурсию, и они довольно изумительны, является результатом хорошо функционального и модульного мышления. Я очень ценю обмен.

Я хотел бы добавить, что recursion не будет работать для больших строк, вызовы стека будут переполняться; поэтому я решил попробовать итеративный подход … и это то, что я получаю.

Код довольно понятный, я добавил некоторые встроенные комментарии, чтобы попытаться заверить это.

Если вы этого не сделаете, сообщите мне об этом, и я улучшу читаемость (возможно, у меня есть вводящая в заблуждение интерпретация моего собственного кода).

 import java.util.Random; public class Solution { public static class Node> implements Comparable> { T data; Node next; @Override public int compareTo(Node 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 first = new Node<>(); first.data = 0; first.next = null; Node current = first; Integer last = first.data; for (int i = 1; i < size; i++) { Node node = new Node<>(); node.data = last + r.nextInt(5); last = node.data; node.next = null; current.next = node; current = node; } return first; } 

}

Почему все эти решения настолько сложны? Вы не хотите использовать рекурсию здесь, потому что вы можете слишком сильно переусердствовать и выбросить исключение переполнения стека. Каждое решение использует слишком много строк кода или использует рекурсию. Это чрезвычайно простая реализация Java с уже включенными декларациями и инициализациями.

  LinkedList list1 = new LinkedList(); LinkedList list2 = new LinkedList(); LinkedList sortedList = new LinkedList(); 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); 

Печать: 1 2 3 4 5 6 7 8 9 10

 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; } 

Прежде всего, понимайте среднее значение «без создания каких-либо новых дополнительных узлов». Насколько я понимаю, это не означает, что я не могу иметь указатель (указатели), который указывает на существующий узел (узлы).

Вы не можете достичь этого, не указав указатели на существующие узлы, даже если вы используете рекурсию для достижения того же самого, система создаст для вас указатели как стеки вызовов. Это точно так же, как сказать системе добавить указатели, которых вы избегали в своем коде.

Простая функция для достижения того же результата с помощью дополнительных указателей :

 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; } в 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; } 
 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; } 

Пожалуйста, обратитесь к моему сообщению в блоге для http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html

 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; } } 

Ниже приведен полный рабочий пример, в котором используется связанный список java.util. Вы можете просто скопировать код ниже внутри метода main ().

  LinkedList dList1 = new LinkedList(); LinkedList dList2 = new LinkedList(); LinkedList dListMerged = new LinkedList(); 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); } 

Рекурсивный путь (вариант ответа Стефана)

  MergeList(Node nodeA, Node nodeB ){ if(nodeA==null){return nodeB}; if(nodeB==null){return nodeA}; if(nodeB.data 

Рассмотрим приведенный ниже список, чтобы визуализировать этот

2>4 список A 1>3 список B

Почти такой же ответ (не рекурсивный), как у Стефана, но с меньшим количеством комментариев / значимого имени переменной. Также рассматривается двойной связанный список в комментариях, если кто-то заинтересован

Рассмотрим пример

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 в 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 

Я беру на себя следующий вопрос:

псевдокод:

 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. 

Код:

 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; } 
  /* 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; } } 
 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->datadata) { h3=h1; h1=h1->next; } else { h3=h2; h2=h2->next; } LLNode *oh=h3; while(h1!=NULL && h2!=NULL) { if(h1->datadata) { 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; } 
 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; } 
 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(); } 

Вот код о том, как объединить два отсортированных связанных списка headA и 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; } 
Давайте будем гением компьютера.