[数据结构与算法]合并两个有序链表---2022/02/24

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题目来源

解题思考

思路：
第一种方法：边比较边放入新的链表（这里存在一个比较边界的问题） 但是这里的时间复杂度为n的平方。方法描述在进行添加之前判断链表是否有效，如果链表1（2）已经指向末尾，把链表2（1）剩下元素全部添加到新建链表中，并直接返回。如果链表1当前元素<链表2当前元素，链表1当前元素添加新链表中，链表1指向下一个元素，否则链表2当前元素添加新链表中，链表2指向下一个元素

第二种方法：分别取出链表1和链表2的数据放到list(补充:这里最好不选择list，因为调用排序接口只针对数组)里面，然后进行排序，排序结束之后，再逐一添加到新建链表中，返回头节点。时间复杂度为n。且操作更为简洁。

知识补充

1、list、set、map的区别。

以及如何创建。

创建list
List <> a=new ArrayList<>();
创建set
Set <> a=new LinkedHashSet<>();
创建map
Map <> a=new HashMap<>();

2、如何在方法外添加节点的方法（就是cur和head目前的联系关系自己还是有点懵）

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    	int []temp=new int [100];
        int j=0;
    	while(list1!=null)
    	{
    		temp[j++]=list1.val;
    		list1=list1.next;
    	}
    	while(list2!=null)
    	{
    		temp[j++]=list2.val;
    		list2=list2.next;
    	}
    	
        int[] temp1=new int[j];
        for(int k=0;k<j;k++)
        {
        	temp1[k]=temp[k];
        }
        if(temp1.length==0)return null;
    	Arrays.sort(temp1);
    	ListNode head=new ListNode(temp1[0],null);
    	int i=1;
    	ListNode curent=head;
    	
    	//由于节点类没有定义其后添加节点的方法
    	//所以在这里一直打圈圈，走不出来。。。。
    	//而后解决了，但是还是不是很清楚，head和curent如何对上的？
    	while(i<j)
    	{
    		ListNode newNode = new ListNode(temp1[i]);    
     		curent.next  = newNode;
     		curent=curent.next;
    		i++;
    	}
		return head;
    }
}

性能评估

依旧是以内存换取时间。