Merge two ordered linked lists ---2022/02/24

Title Description

Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists .
Title source

Problem solving thinking

Ideas ：
The first method ： Add a new linked list while comparing （ There is a problem of comparing boundaries ） But the time complexity here is n The square of . Method description to determine whether the linked list is valid before adding , If linked list 1（2） Has pointed to the end , Put the linked list 2（1） All the remaining elements are added to the new linked list , And return directly . If linked list 1 The current element < Linked list 2 The current element , Linked list 1 The current element is added to the new linked list , Linked list 1 Point to the next element , Otherwise the linked list 2 The current element is added to the new linked list , Linked list 2 Point to the next element

The second method ： Take out the linked list respectively 1 And the list 2 Put your data in list( Add : It is better not to choose list, Because the sorting interface is called only for arrays ) Inside , And then sort it , After sorting , And then add them to the new linked list one by one , Return to the header node . The time complexity is n. And the operation is more concise .

Knowledge supplement

1、list、set、map The difference between .

And how to create .

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

2、 How to add a node method outside the method （ Namely cur and head I am still a little confused about my current relationship ）

Code implementation

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;
    	
    	// Because the node class does not define a method for adding nodes after it 
    	// So I keep making circles here , I can't walk out ....
    	// Then it was solved , But still not very clear ,head and curent How to match ？
    	while(i<j)
    	{
    
    		ListNode newNode = new ListNode(temp1[i]);    
     		curent.next  = newNode;
     		curent=curent.next;
    		i++;
    	}
		return head;
    }
}

Performance evaluation

It is still a trade-off between memory and time .