LeetCode - Easy - 21. Merge Two Sorted Lists

小灰灰 2023-01-05 15:28 122阅读 0赞

## Topic ##

*  Linked List
 *  Recursion

## Description ##

[https://leetcode.com/problems/merge-two-sorted-lists/][https_leetcode.com_problems_merge-two-sorted-lists]

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

**Example 1**:

![c8c4179fe3b26bb737eb49cfc0105f4e.png][]

Input: l1 = [1,2,4], l2 = [1,3,4]
    Output: [1,1,2,3,4,4]

**Example 2**:

Input: l1 = [], l2 = []
    Output: []

**Example 3**:

Input: l1 = [], l2 = [0]
    Output: [0]

**Constraints**:

*  The number of nodes in both lists is in the range \[0, 50\].
 *  \-100 <= Node.val <= 100
 *  Both l1 and l2 are sorted in **non-decreasing** order.

## Analysis ##

联想现实生活当中的拉链

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class MergeTwoSortedLists { 
    	
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
    		if (l1 == null) { 
    			return l2;
    		} else if (l2 == null) { 
    			return l1;
    		} else if (l1.val < l2.val) { 
    			l1.next = mergeTwoLists(l1.next, l2);
    			return l1;
    		} else { 
    			l2.next = mergeTwoLists(l1, l2.next);
    			return l2;
    		}
    	}
    
    	/** * 初次回答 * * @param l1 * @param l2 * @return */
    	public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { 
    		ListNode result = null, pointer1 = l1, pointer2 = l2, resultPointer = null;
    
    		while (!(pointer1 == null && pointer2 == null)) { 
    
    			int tmp = 0;
    
    			if (pointer1 != null && pointer2 == null) { 
    				tmp = pointer1.val;
    				pointer1 = pointer1.next;
    			}
    
    			if (pointer1 == null && pointer2 != null) { 
    				tmp = pointer2.val;
    				pointer2 = pointer2.next;
    			}
    
    			if (pointer1 != null && pointer2 != null) { 
    				if (pointer1.val < pointer2.val) { 
    					tmp = pointer1.val;
    					pointer1 = pointer1.next;
    				} else { 
    					tmp = pointer2.val;
    					pointer2 = pointer2.next;
    				}
    			}
    
    			if (result == null) { 
    				result = new ListNode(tmp);
    				resultPointer = result;
    			} else { 
    				resultPointer.next = new ListNode(tmp);
    				resultPointer = resultPointer.next;
    			}
    
    		}
    
    		return result;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList;
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class MergeTwoSortedListsTest { 
    
    	@Test
    	public void test() { 
    		MergeTwoSortedLists ml = new MergeTwoSortedLists();
    		
    		ListNode L1 = SinglyLinkedList.intArray2List(new int[] { 1, 2, 4});
    		ListNode L2 = SinglyLinkedList.intArray2List(new int[] { 1, 3, 4});
    		
    		ListNode expected = SinglyLinkedList.intArray2List(new int[] { 1, 1, 2, 3, 4, 4});
    		
    		assertTrue(SinglyLinkedList.areTwoListEqual(expected, ml.mergeTwoLists(L1, L2)));
    	}
    	@Test
    	public void test2() { 
    		MergeTwoSortedLists ml = new MergeTwoSortedLists();
    		
    		ListNode L1 = SinglyLinkedList.intArray2List(new int[] { 2, 4, 6, 8});
    		ListNode L2 = SinglyLinkedList.intArray2List(new int[] { 1, 3, 5, 7});
    		
    		ListNode expected = SinglyLinkedList.intArray2List(new int[] { 1, 2, 3, 4, 5, 6, 7, 8});
    		
    		assertTrue(SinglyLinkedList.areTwoListEqual(expected, ml.mergeTwoLists(L1, L2)));
    	}
    }

[https_leetcode.com_problems_merge-two-sorted-lists]: https://leetcode.com/problems/merge-two-sorted-lists/
[c8c4179fe3b26bb737eb49cfc0105f4e.png]: /images/20221119/c1223e8ef8984165a8cd53c9af4902c9.png