Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/21.html
21. Merge Two Sorted Lists
Level
Easy
Description
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Solution
Create a dummyHead
that occurs before the real head of the merged list. Use two pointers temp1
and temp2
to point to the current numbers in the two lists. Initially temp1
and temp2
point to the two lists’ heads respectively. While both temp1
and temp2
are in the lists, compare the numbers at temp1
and temp2
, add the smaller number to the merged list, and move the corresponding pointer one step ahead. If one pointer reaches the end of the list, which is null
, then add the numbers of the other pointer to the merged list. Finally, return dummyHead.next
.
two pointers
big-o analysis
current = current.next; // now current is the new end node, but still pointing to next node
current.next = null; // @note: key, cut this node from l1 or l2
Code
-
public class Merge_Two_Sorted_Lists { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ // Time complexity : O(N) public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (l1 != null || l2 != null) { int v1 = (l1 == null? Integer.MAX_VALUE : l1.val); int v2 = (l2 == null? Integer.MAX_VALUE : l2.val); if (v1 < v2) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; // now current is the new end node, but still pointing to next node current.next = null; // @note: key, cut this node from l1 or l2 } return dummy.next; } } public class Solution_extraSpace { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (l1 != null || l2 != null) { int v1 = l1 == null ? Integer.MAX_VALUE : l1.val; int v2 = l2 == null ? Integer.MAX_VALUE : l2.val; if (v1 < v2) { current.next = new ListNode(v1); // requires extra o(N) space l1 = l1.next; } else { current.next = new ListNode(v2); l2 = l2.next; } current = current.next; } return dummy.next; } } } ############ /** * 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) { ListNode dummy = new ListNode(); ListNode curr = dummy; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { curr.next = list1; list1 = list1.next; } else { curr.next = list2; list2 = list2.next; } curr = curr.next; } curr.next = list1 == null ? list2 : list1; return dummy.next; } }
-
// OJ: https://leetcode.com/problems/merge-two-sorted-lists/ // Time: O(A + B) // Space: O(1) class Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail = &head; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return head.next; } };
-
# without ops after while loop class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() current = dummy while list1 or list2: v1 = list1.val if list1 else float('inf') v2 = list2.val if list2 else float('inf') if v1 < v2: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next current = current.next return dummy.next ############ # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists( self, list1: Optional[ListNode], list2: Optional[ListNode] ) -> Optional[ListNode]: dummy = ListNode() curr = dummy while list1 and list2: if list1.val <= list2.val: curr.next = list1 list1 = list1.next else: curr.next = list2 list2 = list2.next curr = curr.next curr.next = list1 or list2 return dummy.next """ curr.next = list1 or list2 better than: if list1: current.next = list1 if list2: current.next = list2 """
-
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { dummy := &ListNode{} curr := dummy for list1 != nil && list2 != nil { if list1.Val <= list2.Val { curr.Next = list1 list1 = list1.Next } else { curr.Next = list2 list2 = list2.Next } curr = curr.Next } if list1 != nil { curr.Next = list1 } else { curr.Next = list2 } return dummy.Next }
-
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function mergeTwoLists( list1: ListNode | null, list2: ListNode | null, ): ListNode | null { if (list1 == null || list2 == null) { return list1 || list2; } if (list1.val < list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } }
-
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function (list1, list2) { const dummy = new ListNode(); let curr = dummy; while (list1 && list2) { if (list1.val <= list2.val) { curr.next = list1; list1 = list1.next; } else { curr.next = list2; list2 = list2.next; } curr = curr.next; } curr.next = list1 || list2; return dummy.next; };
-
# Definition for singly-linked list. # class ListNode # attr_accessor :val, :next # def initialize(val = 0, _next = nil) # @val = val # @next = _next # end # end # @param {ListNode} list1 # @param {ListNode} list2 # @return {ListNode} def merge_two_lists(list1, list2) dummy = ListNode.new() cur = dummy while list1 && list2 if list1.val <= list2.val cur.next = list1 list1 = list1.next else cur.next = list2 list2 = list2.next end cur = cur.next end cur.next = list1 || list2 dummy.next end
-
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } cur.next = list1 == null ? list2 : list1; return dummy.next; } }
-
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn merge_two_lists( list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { match (list1, list2) { (None, None) => None, (Some(list), None) => Some(list), (None, Some(list)) => Some(list), (Some(mut list1), Some(mut list2)) => { if list1.val < list2.val { list1.next = Self::merge_two_lists(list1.next, Some(list2)); Some(list1) } else { list2.next = Self::merge_two_lists(Some(list1), list2.next); Some(list2) } } } } }