# 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.* **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 } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://a.b.cr/dictionary/algorithm/diary/2022/05/2022-05-24.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.