2022-05-24
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
list1andlist2are sorted in non-decreasing order.
/**
* 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
}
/**
* 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
}
}
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?
/**
* 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
}
/**
* 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)
}
}
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
func runningSum(nums []int) []int {
for i := 1; i < len(nums); i++ {
nums[i] = nums[i] + nums[i-1]
}
return nums
}
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^5ransomNoteandmagazineconsist of lowercase English letters.
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
}
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
/**
* 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
}
/**
* 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 modified 10mo ago