Wonderland
Search
K

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 <= 100
  • Both list1 and list2 are 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: 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
}

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
}