链表排序

//默认l是头节点值较小的链表
func merge(l, r *ListNode) *ListNode{
    tmp := l
    for tmp.Next != nil && r != nil{
        tmpN := r.Next
        if tmp.Val <= r.Val && tmp.Next.Val > r.Val{
            r.Next = tmp.Next
            tmp.Next = r
            r = tmpN
        }else{
            tmp = tmp.Next
        }
    }

    if tmp.Next == nil{
        tmp.Next = r
    }

    return l
}

链表反转

func reverse(head *ListNode) *ListNode{
    if head == nil{
        return head
    }

    pre := head.Next
    head.Next = nil
    for pre != nil{
        tmp := pre.Next
        pre.Next = head
        head = pre
        pre = tmp
    }
    return head
}

二分查找

func findLower(nums []int, target int) int {
	l, r := 0, len(nums)-1

	if nums[l] > target {
		return -1
	}

	for l <= r {
		mid := (r-l)/2 + l

		if nums[mid] < target {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	// 判断一下 nums[left] 是不是 target
	if l >= 0 && l < len(nums) && nums[l] == target {
		return l
	}
	// 如果没有找到，就返回第一个小于 target 的位置，如果不需要返回第一个小于 target 的位置，那就返回-1
	return r
}

func findUpper(nums []int, target int) int {
	l, r := 0, len(nums)-1

	if nums[r] < target {
		return -1
	}

	for l <= r {
		mid := (r-l)/2 + l

		if nums[mid] > target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	if r >= 0 && r < len(nums) && nums[r] == target {
		return r
	}
	//如果没有找到，就返回第一个大于 target 的位置，如果不需要返回第一个小于 target 的位置，那就返回-1
	return l
}

快速幂

func quickMul(x float64, N int) float64 {
    ans := 1.0
    // 贡献的初始值为 x
    x_contribute := x
    // 在对 N 进行二进制拆分的同时计算答案
    for N > 0 {
        if N & 1 == 1 {
            // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
            ans *= x_contribute
        }
        // 将贡献不断地平方
        x_contribute *= x_contribute
        // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
        N  = N >> 1
    }
    return ans
}

单链表排序

https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tqId=1008897&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

注意fast是head.Next，正常应该fast，slow都是head