2022-05-24
Description
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a 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 <= 100Both
list1andlist2are sorted in non-decreasing order.
Solution
Approach #0
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
root := &ListNode{}
cur := root
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
cur.Next = list1
cur = cur.Next
list1 = list1.Next
} else {
cur.Next = list2
cur = cur.Next
list2 = list2.Next
}
}
if list1 != nil {
cur.Next = list1
}
if list2 != nil {
cur.Next = list2
}
return root.Next
}Approach #1: Recursive
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
if list1.Val < list2.Val {
list1.Next = mergeTwoLists(list1.Next, list2)
return list1
} else {
list2.Next = mergeTwoLists(list1, list2.Next)
return list2
}
}
Description
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]Example 2:
Input: head = [1,2]
Output: [2,1]Example 3:
Input: head = []
Output: [] Constraints:
The number of nodes in the list is the range
[0, 5000].-5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution
Approach #0: Iterative
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
cur := head
var prev *ListNode
for cur.Next != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
cur.Next = prev
return cur
}Approach #1: Recursive
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return head
}
return reverse(head, nil)
}
func reverse(cur, prev *ListNode) *ListNode {
next := cur.Next
cur.Next = prev
if next == nil {
return cur
} else {
return reverse(next, cur)
}
}Description
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]Constraints:
1 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6
Solution
Approach #0
func runningSum(nums []int) []int {
for i := 1; i < len(nums); i++ {
nums[i] = nums[i] + nums[i-1]
}
return nums
}Description
Given two strings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Example 1:
Input: ransomNote = "a", magazine = "b"
Output: falseExample 2:
Input: ransomNote = "aa", magazine = "ab"
Output: falseExample 3:
Input: ransomNote = "aa", magazine = "aab"
Output: trueConstraints:
1 <= ransomNote.length, magazine.length <= 10^5ransomNoteandmagazineconsist of lowercase English letters.
Solution
Approach #0
func canConstruct(ransomNote string, magazine string) bool {
var m [26]int
for i := 0; i < len(magazine); i++ {
m[magazine[i]-'a']++
}
for i := 0; i < len(ransomNote); i++ {
m[ransomNote[i]-'a']--
if m[ransomNote[i]-'a'] < 0 {
return false
}
}
return true
}Description
A binary tree is uni-valued if every node in the tree has the same value.
Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.
Example 1:
Input: root = [1,1,1,1,1,null,1]
Output: trueExample 2:
Input: root = [2,2,2,5,2]
Output: falseConstraints:
The number of nodes in the tree is in the range
[1, 100].0 <= Node.val < 100
Solution
Approach #0: BFS
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree(root *TreeNode) bool {
queue := []*TreeNode{root}
v := root.Val
for i := 0; i < len(queue); i++ {
if queue[i].Val != v {
return false
}
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
}
return true
}Approach #1: DFS
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree(root *TreeNode) bool {
if root == nil {
return true
}
if root.Left != nil && root.Val != root.Left.Val || !isUnivalTree(root.Left) {
return false
}
if root.Right != nil && root.Val != root.Right.Val || !isUnivalTree(root.Right) {
return false
}
return true
}Last updated