LeetCode - Easy - 21. Merge Two Sorted Lists

Topic

• Linked List
• Recursion

Description

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:

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)));
	}
}