Объединение двух отсортированных связанных списков
Это один из вопросов программирования, заданных во время письменного тестирования от 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 < list2.data){
mergedList->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;
}
Я очень уверен, что это может быть улучшено. Пожалуйста, помогите мне найти, какие строки избыточно я добавил. Пожалуйста, не стесняйтесь критиковать мои синтаксические ошибки и логику.
Спасибо!
18 ответов
Ваш код перегружен if-s вставлены для обработки "особых" случаев, что сильно раздувает и затрудняет чтение. Обычно это происходит, когда вы решаете обрабатывать особые случаи "по коду", а не находите способ обрабатывать их "по данным". В заявлении, приписываемом Дэвиду Уилеру, говорится: "Все проблемы в информатике могут быть решены с помощью другого уровня косвенности". Этот "дополнительный уровень косвенности" обычно очень хорошо работает со списками, помогая значительно уменьшить беспорядок, создаваемый этими ifs.
Чтобы проиллюстрировать вышесказанное, вот как будет выглядеть мой код
#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 <stdio.h>
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) глубина стека, которая может вызвать переполнение стека. Кроме того, это не хвостовая рекурсия, поэтому она не оптимизируется компилятором.
Используйте рекурсию. Код выглядит следующим образом:
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;
}
Таким образом, объединяя полиген с 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)}
Я не могу претендовать на кредит на этот, но он является самым кратким и показывает симметрию между двумя аргументами, не вводит каких-либо неясных вспомогательных функций. Я не уверен, что оптимизирующий компилятор увидит здесь хвостовую рекурсию, но я вижу. Отступ - последний штрих.
Мое решение Golang для этой проблемы:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
head1 := list1
head2 := list2
ans := &ListNode{}
tail := ans
for head1 != nil && head2 != nil {
if head1.Val > head2.Val {
tail.Next = head2
head2 = head2.Next
tail = tail.Next
} else {
tail.Next = head1
head1 = head1.Next
tail = tail.Next
}
}
if head1 != nil {
tail.Next = head1
}
if head2 != nil {
tail.Next = head2
}
return ans.Next
}
Данный список: список1 = 1->2->3 список2 = 1->2->4->5
Вывод: 1->1->2->2->3->4->5
Определите пустой список и поместите элемент последним, если выполняется любое из следующих условий.
В конце верните an.next, который будет текущим заголовком вновь созданного списка.
Итеративное решение для объединения двух отсортированных связанных списков:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(-200)
prev = head
while l1 and l2:
if l1.val <=l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
prev.next = l1 if l1 is not None else l2
return head.next
#include<stdio.h>
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;i<size;i++)
{
printf("List 1\n");
printf("Please enter the value number %d \n",i+1);
scanf("%d",&value);
newNode=(NODE*)malloc(sizeof(NODE));
newNode->data=value;
newNode->next=NULL;
if(i!=0)
{
ptr->next=newNode;
ptr=ptr->next;
}
if(i==0)
{
head1=newNode;
ptr=newNode;
}
}
for(i=0;i<size;i++)
{
printf("\n\nList 2\n");
printf("Please enter the value number %d \n",i+1);
scanf("%d",&value);
newNode=(NODE*)malloc(sizeof(NODE));
newNode->data=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* 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;
}
Это мой дубль. В отличие от других решений, он идентифицирует и пропускает последовательные узлы в одном списке, которые меньше или равны головному узлу другого списка. Заголовок другого списка прикрепляется в конце такой последовательности, и процесс повторяется после смены ролей. Этот подход минимизирует количество назначений 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;
}
Я создал для него функцию рекурсии. Вот мое решение:
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() / вызывающей функции) и просмотрите связанный список по новому указателю для печати данных, это приведет к сортировке объединенного связанного списка.
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: я не смог придумать решение Java для программ, перечисленных выше в C, которые использовали указатели.
Здесь у меня есть весь код для объединения двух отсортированных связанных списков со всеми возможными случаями.
Я взял два указателя "голова" и "хвост", чтобы указать на окончательный отсортированный список, и нет нового связанного списка, который создается, head1 и head2 - это указатели на головы связанных списков, которые передаются функциям слияния в качестве входных данных.
И два связанных списка также берутся у пользователя в качестве входных данных с помощью функции takeInput, и список печатается с помощью функции печати.
#include<iostream>
using namespace std;
//this is the creation of node class which is used to create a node of the linked list
class Node
{
public:
int data;
Node * next;
Node(int data)
{
this -> data = data;
next = NULL;
}
};
//this is the creation of linked list
//-1 is used as the termimator or to stop taking input
Node * takeInput()
{
int data;
cout<<"Enter the data of the node to be inserted (use -1 as the terminator) : ";
cin>>data;
Node * head = NULL;
Node * tail = NULL;
while(data != -1)
{
Node * newNode = new Node(data);
if(head == NULL)
{
head = newNode;
tail = newNode;
}
else
{
tail -> next = newNode;
tail = tail -> next;
}
cout<<"Enter the data of the node to be inserted (use -1 as the terminator) : ";
cin>>data;
}
return head;
}
//this is the function that helps in printing the linked list
void printLinkedList(Node * head)
{
if(head == NULL)
{
return;
}
Node * temp = head;
while(temp != NULL)
{
cout<<temp -> data<<" ";
temp = temp -> next;
}
cout<<endl;
}
//this is the function where two sorted ascending ordered linked list are merged
Node * mergeSortedLinkedList(Node * head1 , Node * head2)
{
Node * head = NULL; //head of the merged linked list
Node * tail = NULL; //tail of the merged linked list
if(head1 == NULL && head2 == NULL) //condition when both the linked list are empty
{
cout<<"cannot merge empty linked list ! "<<endl;
return head;
}
if(head1 == NULL and head2 != NULL) //condition when first linked list is empty
{
head = head2;
return head;
}
if(head2 == NULL and head1 != NULL) //condition when second linked list is empty
{
head = head1;
return head;
}
if(head1->data < head2-> data) //for the first iteration to assign the merged linked list head and tail
{
head = head1;
tail = head1;
head1 = head1 -> next;
}
else
{
head = head2;
tail = head2;
head2 = head2 -> next;
}
while(head1 != NULL and head2 != NULL) //from here it takes care of the whole processes
{
if(head1->data <= head2-> data)
{
tail -> next = head1;
tail = tail -> next;
head1 = head1 -> next;
}
else
{
tail -> next = head2;
tail = tail -> next;
head2 = head2 -> next;
}
}
if(head1 == NULL) //if 1st linked list is smaller than the second linked list
{
tail -> next = head2;
}
if(head2 == NULL) //if 2nd linked list is smaller than the first linked list
{
tail -> next = head1;
}
return head;
}
//this is the main from where all the functions are called accordingly
int main()
{
cout<<"Enter the data of the first linked list ! (make sure its sorted and is in ascending order) "<<endl;
Node * head1 = takeInput();
cout<<"The first Linked List is : ";
printLinkedList(head1);
cout<<endl<<"********************************************************************************************"<<endl;
cout<<"********************************************************************************************"<<endl;
cout<<"Enter the data of the second linked list ! (make sure its sorted and is in ascending order) "<<endl;
Node * head2 = takeInput();
cout<<"The second Liked list is : ";
printLinkedList(head2);
cout<<endl<<"********************************************************************************************"<<endl;
cout<<"********************************************************************************************"<<endl;
Node * head = mergeSortedLinkedList(head1, head2);
cout<<"The resulting sorted linked list is : ";
printLinkedList(head);
cout<<endl<<"--------------------------------------------------------------------------------------------"<<endl;
cout<<"--------------------------------------------------------------------------------------------"<<endl;
}
Это решение на JAVA, и оно работает... где,
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val < list2.val)
{
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
else
{
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
Вы можете использовать Java 8, Stream API для объединения, получения Distinct и сортировки. Ниже приведен пример кода для сортировки и объединения двух списков с элементами Integer.
List<Integer> list1= Arrays.asList(2,3,5,8);
List<Integer> list2 = Arrays.asList(3,6,8);
List<Integer> finalList = new ArrayList<>();
finalList.addAll(list1);
finalList.addAll(list2);
List<Integer> 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<stdio.h>
#include<malloc.h>
#include<stdlib.h>
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->data<node2->data){
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);
}