给定两个分别有n个和m个元素的排序单链表，使用常量空间合并它们。两个列表中的前n个最小元素应成为第一个列表的一部分，其余元素应成为第二个列表的一部分。应保持分类顺序。我们不允许更改第一个链表的指针。
null
例如
Input:First List: 2->4->7->8->10Second List: 1->3->12Output: First List: 1->2->3->4->7Second List: 8->10->12
我们强烈建议您尽量减少浏览器，并先自己尝试。 如果允许我们更改第一个链表的指针，问题就会变得非常简单。如果允许我们更改链接，我们可以简单地执行类似于合并排序算法的合并。我们将前n个最小元素分配给第一个链表，其中n是第一个链表中的元素数，其余元素分配给第二个链表。我们可以在O（m+n）时间和O（1）空间中实现这一点，但这种解决方案违反了我们不能更改第一个列表的链接的要求。
这个问题变得有点棘手，因为我们不允许更改第一个链表中的指针。这个想法类似于 这 但由于我们得到的是单链表，我们不能向后处理LL2的最后一个元素。
对于LL1的每个元素，我们将其与LL2的第一个元素进行比较。如果LL1的元素大于LL2的第一个元素，那么我们交换所涉及的两个元素。为了保持LL2的排序，我们需要将LL2的第一个元素放在正确的位置。我们可以通过遍历LL2一次并更正指针来发现不匹配。
下面是这个想法的实施。
C++
// C++ Program to merge two sorted linked lists without // using any extra space and without changing links // of first list #include <bits/stdc++.h> using namespace std; /* Structure for a linked list node */ struct Node { int data; struct Node *next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // Function to merge two sorted linked lists // LL1 and LL2 without using any extra space. void mergeLists( struct Node *a, struct Node * &b) { // run till either one of a or b runs out while (a && b) { // for each element of LL1, // compare it with first element of LL2. if (a->data > b->data) { // swap the two elements involved // if LL1 has a greater element swap(a->data, b->data); struct Node *temp = b; // To keep LL2 sorted, place first // element of LL2 at its correct place if (b->next && b->data > b->next->data) { b = b->next; struct Node *ptr= b, *prev = NULL; // find mismatch by traversing the // second linked list once while (ptr && ptr->data < temp->data) { prev = ptr; ptr = ptr -> next; } // correct the pointers prev->next = temp; temp->next = ptr; } } // move LL1 pointer to next element a = a->next; } } // Code to print the linked link void printList( struct Node *head) { while (head) { cout << head->data << "->" ; head = head->next; } cout << "NULL" << endl; } // Driver code int main() { struct Node *a = NULL; push(&a, 10); push(&a, 8); push(&a, 7); push(&a, 4); push(&a, 2); struct Node *b = NULL; push(&b, 12); push(&b, 3); push(&b, 1); mergeLists(a, b); cout << "First List: " ; printList(a); cout << "Second List: " ; printList(b); return 0; } |
Python3
# Python3 program to merge two sorted linked # lists without using any extra space and # without changing links of first list # Structure for a linked list node class Node: def __init__( self ): self .data = 0 self . next = None # Given a reference (pointer to pointer) to # the head of a list and an int, push a new # node on the front of the list. def push(head_ref, new_data): # Allocate node new_node = Node() # Put in the data new_node.data = new_data # Link the old list off the new node new_node. next = (head_ref) # Move the head to point to the new node (head_ref) = new_node return head_ref # Function to merge two sorted linked lists # LL1 and LL2 without using any extra space. def mergeLists(a, b): # Run till either one of a # or b runs out while (a and b): # For each element of LL1, compare # it with first element of LL2. if (a.data > b.data): # Swap the two elements involved # if LL1 has a greater element a.data, b.data = b.data, a.data temp = b # To keep LL2 sorted, place first # element of LL2 at its correct place if (b. next and b.data > b. next .data): b = b. next ptr = b prev = None # Find mismatch by traversing the # second linked list once while (ptr and ptr.data < temp.data): prev = ptr ptr = ptr. next # Correct the pointers prev. next = temp temp. next = ptr # Move LL1 pointer to next element a = a. next # Function to print the linked link def printList(head): while (head): print (head.data, end = '->' ) head = head. next print ( 'NULL' ) # Driver code if __name__ = = '__main__' : a = None a = push(a, 10 ) a = push(a, 8 ) a = push(a, 7 ) a = push(a, 4 ) a = push(a, 2 ) b = None b = push(b, 12 ) b = push(b, 3 ) b = push(b, 1 ) mergeLists(a, b) print ( "First List: " , end = '') printList(a) print ( "Second List: " , end = '') printList(b) # This code is contributed by rutvik_56 |
输出：
First List: 1->2->3->4->7->NULLSecond List: 8->10->12->NULL
时间复杂性： O（明尼苏达州）
本文由 阿迪蒂亚·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
