# 2022-05-24

## 21. Merge Two Sorted Lists

### 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.

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.

### Solution

#### Approach #0

``````/**
* 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

``````/**
* 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

``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
return nil
}
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

``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
}
}

func reverse(cur, prev *ListNode) *ListNode {
next := cur.Next
cur.Next = prev
if next == nil {
return cur
} else {
return reverse(next, cur)
}
}``````

## 1480. Running Sum of 1d Array

### 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
}``````

## 383. Ransom Note

### 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: false``````

Example 2:

``````Input: ransomNote = "aa", magazine = "ab"
Output: false``````

Example 3:

``````Input: ransomNote = "aa", magazine = "aab"
Output: true``````

Constraints:

• `1 <= ransomNote.length, magazine.length <= 10^5`

• `ransomNote` and `magazine` consist 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
}``````

## 965. Univalued Binary Tree

### 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: true``````

Example 2:

``````Input: root = [2,2,2,5,2]
Output: false``````

Constraints:

• 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