采访：合并两个sorting的单一链接列表
这是一个面试书面testing中遇到的编程问题。 “你有两个已经sorting好的单链表，你必须合并它们并返回一个新列表的头部，而不会创build任何新的额外节点，返回的列表也应该sorting”
方法签名是：Node MergeLists（Node list1，Node list2）;
节点类如下：
class Node{ int data; Node next; } 我尝试了很多解决scheme，但没有创build额外的节点螺丝钉的东西 请帮忙。
以下是随附的博客文章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; } }
不需要recursion来避免分配新节点：
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, 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; }
下面是关于如何合并两个sorting链接列表A和B的algorithm：
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将是输出列表。
看看马，没有recursion！
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; }
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; }
一个简单的迭代解决scheme。
Node * MergeLists（Node * A，Node * B）{//处理angular落案例
//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 }
}
这可以在不创build额外的节点的情况下完成，只有另一个节点引用传递给参数（节点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; }
我想分享我认为的解决scheme…我看到涉及recursion的解决scheme，他们是相当惊人的，是良好的function和模块化思维的结果。 我非常感谢分享。
我想补充说，recursion不适用于大的lits，堆栈调用将溢出; 所以我决定尝试迭代的方法…这就是我得到的。
代码很自我解释，我添加了一些内联的评论，以确保这一点。
如果你没有得到它，请通知我，我会提高可读性（也许我有一个误导性的解释我自己的代码）。
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; }
}
为什么所有这些解决scheme如此复杂？ 你不希望在这里使用recursion，因为你可能recursion太深，并抛出一个堆栈溢出exception。 每个解决scheme使用太多的代码行或使用recursion。 这是一个非常简单的Java实现，已经包含了声明和初始化。
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);
打印：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; }
首先要理解“不创build任何新的额外节点”的意思 ，据我所知，这并不意味着我不能有指向现有节点的指针。
如果没有指向现有节点的指针，就不能实现它，即使使用recursion实现相同，系统也会为您创build指针，作为调用堆栈。 这就像告诉系统添加你在代码中避免的指针一样。
简单的function来实现相同的采取额外的指针 ：
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<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); }
recursion方式（斯特凡答案的变体）
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; }
考虑下面的链表来可视化这个
2>4清单A 1>3清单B
几乎与Stefan相同的答案（非recursion），但只有更多的评论/有意义的variables名称。 如果有人感兴趣，还包括评论中的双链表
考虑这个例子
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; } }
我的问题如下：
伪代码：
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; } }
public Node NewMerge(Node head1, Node head2) { if (head1 != null && head2 != null) { if (head1.data > head2.data) { head2.next = NewMerge(head1, head2.next); return head2; } else if (head1.data == head2.data) { head1.next = NewMerge(head1.next, head2.next); return head1; } else { head1.next = NewMerge(head1.next, head2); return head1; } } else if (head1 == null) return head2; else return head1; }
我试图在控制台应用程序中运行它，在我启动了两个总共有6400多个节点的NodeList之后，我发现我的控制台应用程序抛出了StackOverflowExceptionexception。 任何人有类似的问题？
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(); }
以下是关于如何合并两个sorting的链接列表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; }
