Sword finger offer | merge two sorted linked lists

Java Language . Iterative method , It's a little different from the idea in the book , Not the simplest , For reference only .

1. describe ：

Enter two monotonically increasing linked lists , Output the synthesized list of two linked lists , Of course, we need the synthesized list to satisfy the monotone rule .

2. example ：

 Input ：  {1,3,5},{2,4,6}
 Return value ：{1,2,3,4,5,6}

3. Ideas

1. Based on the first linked list , Link list 2 Insert into the first linked list .（ Will be less than res1.val Insert the value of before ）
2. Circular linked list 2, Insert each element into the linked list 1 The right place .

4. Code

public class Solution {
    
    public ListNode Merge(ListNode list1,ListNode list2) {
    
        ListNode res = list1;
        ListNode res2 = list2;
        while (res2 != null)   // res2.next == null  At the end of the line 
        {
    
            if (res2.val < res.val)// If less than, insert directly  
            {
    
                int cur = res.val;
                ListNode next = res.next;
                ListNode curres2 = new ListNode(res2.val);
                // Set the temporary node curres2  Insert into  res after 
                res.next = curres2;
                curres2.next = next;
                // Switching nodes curres2  and res Of val
                res.val = curres2.val;
                curres2.val = cur;
                
                res = res.next;
                res2 = res2.next;
            } 
            else  //  Greater than, move the linked list 1 The pointer .
            {
    
                if (res.next != null)  //res Not reaching the end of the team 
                {
    
                    res = res.next;
                }else  // Reach the end of the team , Directly link the remaining elements to the linked list 1 Back 
                {
    
                   res.next = res2;
                   break;
                }

            }
        }

        return list1;
    }
}

to update ： Method 2

Define a temporary linked list , Always attach small nodes to temporary nodes

 public ListNode Merge(ListNode list1, ListNode list2) {
    
	 ListNode phead = new ListNode(-1);
	 ListNode cur = phead;
	 ListNode p1 = list1,p2 = list2;
	 while(p1!=null && p2!=null){
    
	    if(p1.val<p2.val){
    
	       cur.next = new ListNode(p1.val);
	       p1 = p1.next;
	       cur = cur.next;
	    }else{
    
	       cur.next = new ListNode(p2.val);
	       p2 = p2.next;
	       cur = cur.next;
	    }
	}
	if(p1!=null){
    
	  cur.next = p1;
	}
	if(p2!=null){
    
	  cur.next = p2;
	}
	return phead.next;