21.合并两个有序链表(高频)

题目：两个升序链表，合并成一个 https://leetcode-cn.com/problems/merge-two-sorted-lists

题解：

• 需要一个空的头节点做辅助，head.Next就是结果
• 每次遍历始终维护上一个节点prev，初始值prev=head
• 循环遍历两个链表，循环条件都不为空，每次把当前节点更小的取出来即可

prev.Next = l1
prev = l1
l1 = l1.Next

• 最后加入有不为空的节点，则直接赋值

if l1!=nil{
    prev.Next = l1
}else{
    prev.Next = l2
}

完整代码

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
 head := &ListNode{
  Val:0,
  Next:nil,
 }
 prev := head
 for l1!=nil && l2!=nil{
  if l1.Val < l2.Val{
   prev.Next= l1
   prev = l1
   l1 = l1.Next
  }else{
   prev.Next = l2
   prev = l2
   l2 = l2.Next
  }
 }
 if l1!=nil{
  prev.Next = l1
 }else{
  prev.Next = l2
 }
 return head.Next
}

53.最大子序和(高频)

题目：求和加起来最大的连续子数组 https://leetcode-cn.com/problems/maximum-subarray

题解：

• 一次循环，数组里有可能出现负数，且只需要统计和即可
• 需要两个计数器，一个存储全局最大的子序列和，只要出现更大的就更新
• 另一个存储当前最大的子序和，判断当前最大子序和的方法是比较子序和与当前值哪个大
• 有可能当前值比子序列和大，就更新子序 max(nums[i],nums[i]+last)

核心代码

last = max(nums[i],nums[i]+last)
resMax = max(resMax,last)

完整代码

func maxSubArray(nums []int) int {
 n := len(nums)
 if n<1{
  return 0
 }
 last,resMax := nums[0],nums[0]
 for i:=1;i<n;i++{
  // 要不就是自成一派，要不就是和前面连续的放在一起
  last = max(nums[i],nums[i]+last)
  resMax = max(resMax,last)
 }
 return resMax
}
func max(x,y int)int{
 if x>y{
  return x
 }
 return y
}