> For the complete documentation index, see [llms.txt](https://a.b.cr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://a.b.cr/dictionary/algorithm/diary/2022/05/2022-05-24.md).

# 2022-05-24

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/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.

Return *the head of the merged linked list*.

**Example 1:**

![](https://img.content.cc/a/2022/05/24/09-52-03-654-2b038dbe54fad2913610d24cf6831806-823b97.jpeg)

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

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

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

```

## [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

### Description

Given the `head` of a singly linked list, reverse the list, and return *the reversed list*.

**Example 1:**

![](https://img.content.cc/a/2022/05/24/09-52-24-768-49f3322c7abc9a0c7cf637264e677bc2-5a3f8d.jpeg)

```
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
```

**Example 2:**

![](https://img.content.cc/a/2022/05/24/09-52-46-964-dac276cabb172665269e9078356513aa-c97bb0.jpeg)

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

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

```go
/**
 * 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)
    }
}
```

## [1480. Running Sum of 1d Array](https://leetcode.com/problems/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

```go
func runningSum(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        nums[i] = nums[i] + nums[i-1]
    }
    return nums
}
```

## [383. Ransom Note](https://leetcode.com/problems/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

```go
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](https://leetcode.com/problems/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.*&#x20;

**Example 1:**

![](https://img.content.cc/a/2022/05/24/11-47-21-248-5229ab18994b6ea8876a5d6ef753cb14-7c1d35.png)

```
Input: root = [1,1,1,1,1,null,1]
Output: true
```

**Example 2:**

![](https://img.content.cc/a/2022/05/24/11-47-36-955-f40b1953bc650c023d232cb4a03459f6-28a14f.png)

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

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

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