双指针（链表、数组）
二分查找用于有序的排列
python中的二分查找模块bisect,Python中的list.inidex时间复杂度是O(n),bisect复杂度小些
[图片上传失败...(image-580b0b-1562308505200)]
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
return mid
return -1
二分查找的升级版
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
见题#34
86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
def partition(self, head: ListNode, x: int) -> ListNode:
h1 = l1 = ListNode(0)
h2 = l2 = ListNode(0)
while head:
if head.val < x:
l1.next = head
l1 = l1.next
else:
l2.next = head
l2 = l2.next
head = head.next
l2.next = None
l1.next = h2.next
return h1.next
61. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
这个我也能写出来，但是就是不如人家写的规范，关于什么时候定义的指针是当前指向head,还是下一步指向head还混淆
很厉害，人家是先连起来，再找头
class Solution:
def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':
# base cases
if not head or not head.next:
return head
# close the linked list into the ring
old_tail = head
n = 1
while old_tail.next:
old_tail = old_tail.next
n += 1
old_tail.next = head
# find new tail : (n - k % n - 1)th node
# and new head : (n - k % n)th node
new_tail = head
for i in range(n - k % n - 1):
new_tail = new_tail.next
new_head = new_tail.next
# break the ring
new_tail.next = None
return new_head
归并算法的两种类型 top-down（递归）、bottom-up(迭代)
用在链表里的归并算法空间复杂度可以是O(1)
148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
其实我觉得两种写法空间复杂度都是O(n)
递归写法
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
cut = slow = fast = head
while fast and fast.next:
cut = slow
fast = fast.next.next
slow = slow.next
cut.next = None
left = self.sortList(head)
right = self.sortList(slow)
return self.merge(left, right)
def merge(self, left, right):
m = n = ListNode(0)
while left and right:
if left.val <= right.val:
n.next = left
left = left.next
else:
n.next = right
right = right.next
n = n.next
n.next = left or right
return m.next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None: return None
def getSize(head):
counter = 0
while(head is not None):
counter +=1
head = head.next
return counter
def split(head, step):
i = 1
while (i < step and head):
head = head.next
i += 1
if head is None: return None
#disconnect
temp, head.next = head.next, None
return temp
def merge(l, r, head):
cur = head
while(l and r):
if l.val < r.val:
cur.next, l = l, l.next
else:
cur.next, r = r, r.next
cur = cur.next
cur.next = l if l is not None else r
while cur.next is not None: cur = cur.next
return cur
size = getSize(head)
bs = 1
dummy = ListNode(0)
dummy.next = head
l, r, tail = None, None, None
while (bs < size):
cur = dummy.next
tail = dummy
while cur:
l = cur
r = split(l, bs)
cur = split(r, bs)
tail = merge(l, r, tail)
bs <<= 1
return dummy.next
