21. Merge Two Sorted Lists

題目

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

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

解法(Java)

這題想要合併兩個單向鏈結陣列，一開始是想要在list1進行操作，但發現不太行，最後改採合併至新的鏈結陣列。

Runtime: 0 ms
Memory Usage: 41.2 MB (69.54%)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    	if (list1 == null) return list2;
    	if (list2 == null) return list1;
    	
    	ListNode result = new ListNode();
    	ListNode resultCurr = result;
    	
    	while (list1 != null && list2 != null) {
    		if (list1.val <= list2.val) {
    			resultCurr.next = list1;
    			list1 = list1.next;
    		} else {
    			resultCurr.next = list2;
    			list2 = list2.next;
    		}
    		resultCurr = resultCurr.next;
    	}
    	
    	resultCurr.next = list1 != null ? list1 : list2;
    	
    	return result.next;
    }
}

2. Add Two Numbers

題目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

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

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

解法(Java)

這題雖然是Medium 但也算簡單，只要把值往l1加就好了，不過最後要判斷有沒有進位的問題。

Runtime: 1 ms (100%)
Memory Usage: 42.9 MB (79.98%)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode curr = l1;
    	int sum = 0, num = 0;
    	
    	while (l2 != null) {
    		sum = this.sum(curr, l2, num);
            num = sum >= 10 ? 1 : 0;
            
    		curr.val = sum % 10;
    		if (curr.next == null && (l2.next != null || num == 1)) {
    			curr.next = new ListNode();
    		}
    		curr = curr.next;
			l2 = l2.next;
    	}
    	
    	if (curr != null) {
    		while (curr.next != null) {
        		sum = curr.val + num;
                num = sum >= 10 ? 1 : 0;
                
        		curr.val = sum % 10;
        		curr = curr.next;
        	}
    	}
    	
    	if (num != 0) {
    		sum = curr.val + num;
    		curr.val = sum % 10;
    		if (sum >= 10) curr.next = new ListNode(1);
    	}
    	
    	return l1;
    }
    
    int sum(ListNode l1, ListNode l2, int num) {
    	if (l1 != null && l2 != null) {
    		return l1.val + l2.val + num;
    	} else if (l1 != null && l2 == null) {
    		return l1.val + num;
    	} else {
    		return l2.val + num;
    	}
    }
}

小結

這兩道題目都不難，稍微想一下就有初步的解法可以實作了，不過最近工作開始忙起來了，沒甚麼時間能夠再去優化已經完成的題目，畢竟解題不是只要解完就好，還要挑戰更短的時間跟最少的空間。