合并两个已排序的链接列表
这是Microsoft编写测试期间提出的编程问题之一。 我提出了我想出的问题和答案。 事情虽然看起来很全面（至少对我来说），但我觉得可以减少行数。 它在C中被问到我是一个Java人，但我设法编写它（我的答案可能包含太多类似Java的语法）
好的，这是问题所在。
您有两个已经排序的列表，您必须合并它们并返回一个没有任何新额外节点的新列表。 返回的列表也应该排序。
方法签名是，
Node* MergeLists(Node* list1, Node* list2); struct Node{ int data; Node *next; } 以下是我提出的解决方案，
Node* MergeLists(Node* list1, Node* list2){ Node* mergedList; if(list1 == null && list2 ==null){//if both are null, return null return null; } if(list1 == null){//if list1 is null, simply return list2 return list2; } if(list2 == null){//if list2 is null, simply return list1 return list1; } if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser mergedList = list1; }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal mergedList = list2; } while(list1!=null && list2!=null){ if(list1.data next = list1; list1 = list1->next; }else{ mergedList->next = list2; list2 = list2->next; } } if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end. mergedList->next = list2; }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end mergedList->next = list1; } return mergedList; }
我非常有信心可以加强它。 请帮我查一下我添加的冗余行。 请随意批评我的语法错误和逻辑。
谢谢！
if插入了-s来处理“特殊”情况， if你的代码会被重载，这会使它大量膨胀并使其难以阅读。 当您决定“通过代码”处理特殊情况而不是找到“按数据”处理它们的方法时，通常会发生这种情况。 David Wheeler的一句话说：“计算机科学中的所有问题都可以通过另一层次的间接解决”。 “额外的间接级别”通常可以很好地与列表一起使用，有助于显着减少那些由s创建的混乱。
为了说明上述内容，这是我的代码的样子
#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0) Node* MergeLists(Node* list1, Node* list2) { Node *list = NULL, **pnext = &list; if (list2 == NULL) return list1; while (list1 != NULL) { if (list1->data > list2->data) SWAP_PTRS(list1, list2); *pnext = list1; pnext = &list1->next; list1 = *pnext; } *pnext = list2; return list; }
有些人可能会争辩说，在pnext指针中使用额外级别的间接实际上会使代码更难以阅读。 我同意，对于一个新手来说，这种方法可能会带来一些困难，但对于一个经验丰富的程序员来说，这应该很容易理解为成语。
最明显的错误是在你的循环中，你继续覆盖mergedList-> next，丢失之前添加的节点。 也就是说，无论输入如何，您返回的列表将永远不会包含两个以上的节点…
我做了C已经有一段时间了，但我会这样做：
Node* merge(Node* list1, Node* list2) { Node* merged = null; Node** tail = &merged; while (list1 && list2) { if (list1->data < list2->data) { *tail = list1; list1 = list1->next; } else { *tail = list2; list2 = list2->next; } tail = &((*tail)->next); } *tail = list1 ? list1 : list2; return merged; }
我带着一个测试用例
到目前为止，所有答案都很有趣并且做得很好。 这个可能更像是一个采访者希望看到的，包括DRY / DIE和TDD。 🙂
#include typedef struct ns { int data; struct ns *next; } Node; Node l1[] = { { 1, &l1[1] }, { 3, &l1[2] }, { 5, &l1[3] }, { 7, &l1[4] }, { 9, &l1[5] }, {11, 0 }, }; Node l2[] = { { 2, &l2[1] }, { 4, &l2[2] }, { 6, 0 }, }; Node* MergeLists(Node* list1, Node* list2) { Node *t, **xt; for(xt = &t; list1 || list2;) { Node **z = list1 == NULL ? &list2 : list2 == NULL ? &list1 : list1->data < list2->data ? &list1 : &list2; *xt = *z; xt = &(*z)->next; *z = *xt; } *xt = NULL; return t; } int main(void) { for(Node *t = MergeLists(l1, l2); t; t = t->next) printf("%d\n", t->data); return 0; }
它没有比这更优雅：
Node* merge2(Node* n1, Node* n2) { n1->next = merge(n1->next, n2); return n1; } Node* merge(Node* n1, Node* n2) { return (n1 == null) ? n2 : (n2 == null) ? n1 : (n1->data < n2->data) ? merge2(n1, n2) : merge2(n2, n1); }
假设您理解递归，这很清楚。
我应该指出，这仅适用于面试答案（可能表明思想的清晰度比仅仅表明你知道如何编写程序更有影响）。 实际上，您不希望以这种方式合并，因为它使用O(n)堆栈深度，这可能会导致堆栈溢出。 此外，它不是尾递归，因此它不是编译器可优化的。
Divide et Impera
（即MergeSort ）
所以合并polygen和AndreyT我们得到：
Node* merge(Node* n1, Node* n2) { return (n1 == null) ? n2 : (n2 == null) ? n1 : (n1->data < n2->data) ? (n1->next = merge(n1->next, n2), n1) : (n2->next = merge(n2->next, n1), n2)}
我不能称赞这个，但它是最简洁的并且显示了两个参数之间的对称性，没有引入任何模糊的辅助函数。 我不确定优化编译器会在这里看到尾递归，但我确实如此。 缩进是最后的触摸。
使用递归。 代码如下：
ListNode* mergeTwoSortedLists(ListNode* pHead1, ListNode* pHead2) { if(pHead1 == NULL) return pHead2; else if(pHead2 == NULL) return pHead1; ListNode* pMergedHead = NULL; if(pHead1->m_nValue < pHead2->m_nValue) { pMergedHead = pHead1; pMergedHead->m_pNext = mergeTwoSortedLists(pHead1->m_pNext, pHead2); } else { pMergedHead = pHead2; pMergedHead->m_pNext = mergeTwoSortedLists(pHead1, pHead2->m_pNext); } return pMergedHead; }
public void Merge(LinkList list1, LinkList list2) { if (list1.head == null && list2.head == null) { System.out.println("Empty list"); //Check if lists are empty } if (list1.head == null) { //If list1 is empty print list2 list2.printList(); } if (list2.head == null) { //If list2 is empty print list1 list1.printList(); } LinkList list3 = new LinkList(); //create a new LinkList object for merging Node a = list1.head; //Beginning of list1 Node b = list2.head; //Beginning of list2 while (a != null && b != null) { //Until list ends if (a.value <= b.value) { //Compare values of list1 against list2 list3.insert(a.value); //Insert values to new list a = a.next; } else if (a.value >= b.value) { list3.insert(b.value); b = b.next; } else if (a.value == b.value){ //Insert only unique values and discard repeated values list3.insert(a.value); a = a.next; b = b.next; } } if (a == null) { while (b != null) { list3.insert(b.value); //If list1 becomes empty, attach rest of the list2 to list3 b = b.next; } } if (b == null) { while (a != null) { list3.insert(a.value); a = a.next; } } list3.printList(); //print merged list } }
嗨，大家好 ！ 我本月正准备接受采访，当我正在研究这个问题时，这就是我提出的解决方案。 我将我的解决方案与您在此处发布的许多解决方案进行了比较，并发现我的程 虽然我发现这更容易理解和实现，但是现有代码是否有更好的Java解决方案。 我正在寻找更好的时间复杂度解决方案。 任何帮助/方向/提示表示赞赏。
PS：我无法为C中使用指针的上面列出的程序提供Java解决方案。
这是我的看法。 与其他解决方案不同，它识别并跳过一个列表上的连续节点，这些节点小于或等于另一个列表的头节点。 另一个列表的头部附加在这样的序列的末尾，并且在切换角色之后重复该过程。 这种方法最大限度地减少了Node.next的赋值次数，同时将NULL测试限制为每次迭代中的单次检查。
Node * merge(Node *list1, Node *list2) { if (!list1) return list2; if (!list2) return list1; Node *tmp; // compare head nodes and swap lists to guarantee list1 has the smallest node if (list1->val > list2->val) { tmp = list2; list2 = list1; list1 = tmp; } Node *tail = list1; do { // Advance the tail pointer skipping over all the elements in the result // which have smaller or equal value than the first node on list2 while (tail->next && (tail->next->val <= list2->val)) { tail = tail->next; } // concat list2 at tail of result and make the rest after tail list2 tmp = tail->next; tail->next = list2; tail = list2; list2 = tmp; } while (list2); return list1; }
#include typedef struct NODE { int data; struct NODE * next; }NODE; NODE * func(NODE*,NODE*); int main() { int i; int size; int value; NODE * head1,*head2,*newNode,*ptr,*final; printf("\nPlease enter the number of elements\n"); scanf("%d",&size); for(i=0;idata=value; newNode->next=NULL; if(i!=0) { ptr->next=newNode; ptr=ptr->next; } if(i==0) { head1=newNode; ptr=newNode; } } for(i=0;idata=value; newNode->next=NULL; if(i!=0) { ptr->next=newNode; ptr=ptr->next; } if(i==0) { head2=newNode; ptr=newNode; } } final=func(head1,head2); printf("\n\n"); while (final!=NULL) { printf("%d -->",final->data); final=final->next; } printf("NULL "); return 0; } NODE* func(NODE* list1, NODE* list2) { NODE* mergedList,*mergeHead=NULL; if(list1 == NULL && list2 ==NULL){//if both are NULL, return NULL return NULL; } if(list1 == NULL){//if list1 is NULL, simply return list2 return list2; } if(list2 == NULL){//if list2 is NULL, simply return list1 return list1; } mergedList = (NODE*)malloc(sizeof(NODE)); if(list1->data < list2->data){//initialize mergedList pointer to list1 if list1's data is lesser mergedList->data=list1->data; mergedList->next=NULL; list1 = list1->next; }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal mergedList->data=list2->data; mergedList->next=NULL; list2 = list2->next; } mergeHead=mergedList; while(list1!=NULL && list2!=NULL){ if(list1->data < list2->data){ mergedList->next = (NODE*)malloc(sizeof(NODE)); mergedList=mergedList->next; mergedList->data=list1->data; mergedList->next=NULL; list1 = list1->next; }else{ mergedList->next = (NODE*)malloc(sizeof(NODE)); mergedList=mergedList->next; mergedList->data=list2->data; mergedList->next=NULL; list2 = list2->next; } } if(list1 == NULL){//remaining nodes of list2 appended to mergedList when list1 has reached its end. while(list2!=NULL) { mergedList->next = (NODE*)malloc(sizeof(NODE)); mergedList=mergedList->next; mergedList->data=list2->data; mergedList->next=NULL; list2 = list2->next; } }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end mergedList->next = (NODE*)malloc(sizeof(NODE)); mergedList=mergedList->next; mergedList->data=list1->data; mergedList->next=NULL; list1 = list1->next; } return mergeHead; }
我已经为它创建了递归函数。 这是我的解决方案：
Node* merge_recursion(Node* l1, Node* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->data < l2->data) { l1->next = merge_recursion(l1->next, l2); return l1; } else { l2->next = merge_recursion(l1, l2->next); return l2; } }
将返回指针存储到新的指针变量（在main（）/调用函数中）并遍历新指针上的链接列表以打印数据，它将导致已排序的合并链表。
你可以使用递归：
Node* MergeLists(Node *headA, Node* headB) { if(headA==NULL){ return headB; }else if(headB ==NULL){ return headA; } Node* head = NULL; if(headA->data <= headB->data){ head= headA; head->next = MergeLists(headA->next,headB); }else{ head= headB; head->next = MergeLists(headA,headB->next); } return head; }
您可以使用Java 8，Stream API进行合并，获得Distinct和sort。 下面是使用Integer元素对两个列表进行排序和合并的示例代码
List list1= Arrays.asList(2,3,5,8); List list2 = Arrays.asList(3,6,8); List finalList = new ArrayList<>(); finalList.addAll(list1); finalList.addAll(list2); List mergeSortedList = finalList.stream() .distinct() .sorted() .collect(Collectors.toList()); System.out.println(mergeSortedList);
//I have used recursions . //Sorry for such a long code. //:) it works,hope it helps. #include #include #include struct node{ int data; struct node *next ; }; struct node *start1=NULL,*start2=NULL; struct node*start=NULL; struct node *create_ll1(struct node *start); struct node *create_ll2(struct node *start); void sorted_ll(struct node* node1,struct node* node2); struct node *display(struct node *start); void p(struct node*); main(){ start1=create_ll1(start1); start2=create_ll2(start2); //start1=display(start1); printf("\n"); //start2=display(start2); sorted_ll(start1,start2); //start=display(start); } struct node *create_ll1(struct node *start1){ struct node *ptr,*new_node; int num; printf("Enter -1 for ending \n"); printf("Enter data for list 1: \n"); scanf("%d",&num); while(num!=-1){ new_node=(struct node *)malloc(sizeof(struct node)); new_node->data=num; if(start1==NULL){ new_node->next=NULL ; start1=new_node; } else{ ptr=start1 ; while(ptr->next!=NULL) ptr=ptr->next; ptr->next=new_node; new_node->next=NULL ; } printf("Enter data: \n"); scanf("%d",&num); } return start1; } struct node *create_ll2(struct node *start2){ struct node *ptr,*new_node; int num; printf("Enter -1 for ending \n"); printf("Enter data for list 2: \n"); scanf("%d",&num); while(num!=-1){ new_node=(struct node *)malloc(sizeof(struct node)); new_node->data=num; if(start2==NULL){ new_node->next=NULL ; start2=new_node; } else{ ptr=start2 ; while(ptr->next!=NULL) ptr=ptr->next; ptr->next=new_node; new_node->next=NULL ; } printf("Enter data: \n"); scanf("%d",&num); } return start2; } struct node *display(struct node *start){ struct node *ptr; ptr=start; while(ptr->next!=NULL){ printf("\t %d",ptr->data); ptr=ptr->next; } printf("\t %d",ptr->data); printf("\n"); return start ; } void sorted_ll(struct node* node1,struct node* node2) { if(!node1){ p(node2); exit(0); } else if(!node2){ p(node1); exit(0); } if(node1->datadata){ printf("%d\t",node1->data); sorted_ll(node1->next,node2); } else{ printf("%d\t",node2->data); sorted_ll(node1,node2->next); } } void p(struct node* pme){ while(pme->next!=NULL){ printf("%d \t",pme->data); pme=pme->next; } printf("%d",pme->data); }