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]
GoLang: Merge Two Sorted Linked List
Let’s create a dummy node via new() function in GoLang which expects a pointer type – and it will zero out the allocated memory by default. Then we go through two lists and compare them one by one, and attach to a smaller node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { var dummy = new(ListNode) var p = dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { p.Next = l1 l1 = l1.Next } else { p.Next = l2 l2 = l2.Next } p = p.Next } if l1 != nil { p.Next = l1 } else { p.Next = l2; } return dummy.Next } |
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { var dummy = new(ListNode) var p = dummy for l1 != nil && l2 != nil { if l1.Val < l2.Val { p.Next = l1 l1 = l1.Next } else { p.Next = l2 l2 = l2.Next } p = p.Next } if l1 != nil { p.Next = l1 } else { p.Next = l2; } return dummy.Next }
GoLang: Merge Two Sorted Linked List using Recursion
We can also do this using Recursion. If the begining of the l1 is a smaller node, we attach its next to the merged (recursive) linked list and return it as the “head”.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } if l1.Val < l2.Val { l1.Next = mergeTwoLists(l1.Next, l2) return l1 } l2.Next = mergeTwoLists(l1, l2.Next) return l2 } |
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } if l1.Val < l2.Val { l1.Next = mergeTwoLists(l1.Next, l2) return l1 } l2.Next = mergeTwoLists(l1, l2.Next) return l2 }
Both implementation take O(N+M) time complexity and O(1) space, as we are not allocating new nodes for the merged list. N and M are the lengths for two sorted linked lists respectively.
See also: How to Merge Two Sorted Lists (Recursion and Iterative)?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Minimum Number of Operations to Target Number
Next Post: Teaching Kids Programming - Largest Anagram Group