合并两个链表的算法方法

Question

将两个升序排序的链表合并为一个升序排序的链表，哪种算法比较好？

时间 vs Space 复杂度？

此解决方案减少了 space 程序的复杂性，因为不会创建和分配不必要的新链表。

assume head1 and head2 the head nodes of lists

if(head1==null && head2==null)  return null;
if(head1==null && head2!=null)  return head2;
if(head1!=null && head2==null)  return head1;

    //assigning mergeLists head to min of both head
    SinglyLinkedListNode t1, t2, c;
    if(head1.data<head2.data){
            t1 = head1;
            t2 = head2;
            c = head1;
    }else{
            t1 = head2;
            t2 = head1;
            c = head2;
    }

    //sorting both lists within without creating new list
    while(t1.next!=null){
            if(t1.next.data <= t2.data) t1 = t1.next;
            else{
            SinglyLinkedListNode temp = t1.next;
            t1.next = t2;
            t1 = t1.next;
            t2 = temp;
            }
    }
    t1.next = t2;
    return c;

就时间复杂度而言，这是更好的经典递归方法。

assume a as head1 and b as head2

MergeSorted(Node a, Node b)
    if (a == null && b == null)
                return null;
            if a==null
                return b;
            if b==null
                return a;

            Node c //Combined List // new list
            if((a).data<(b).data)
                c=a;
                (c).next=MergeSorted((a).next,b);
            else
                c=b;
                (c).next=MergeSorted(a,(b).next);      
            return c;

Answer 1

这些都不会创建新列表。 c 只是对列表节点的另一个引用，而不是新对象。

你的第一个语句，检查两个列表中的 null，没有给程序添加任何内容：紧随其后的 if 将自行完成相同的工作。

这两者在时间上都没有优势复杂性；它们在两个列表长度上都是 O(a+b)。区别在于清晰度和可维护性。由于您没有用任何其他术语定义 "better" 的指标，因此该问题没有实际意义。

合并两个链表的算法方法

Algorithm approach to merge two linked list

algorithm

data-structures

linked-list

time-complexity

space-complexity