常见双指针技巧用法，只总结思路，具体边界判定想不清楚的时候稍微画个图就行了

1. 快慢指针判断链表是否含有环、环入口（快慢指针再次相遇即有环；再从头节点和快慢指针的相遇位置同速度向后，相遇点即为环入口）。

2. 快慢指针找链表中点、倒数第k个元素（快指针到达 Null 时慢指针所处位置即为中点；快指针先走k步，然后和慢指针一起同速度向后，快指针到达 Null 时慢指针的位置就是倒数第k个节点）。

3. 左右指针二分查找、在有序数组中找两数之和、反转数组

4. 滑动窗口，典型题包括 #76、#438、#3

76. 最小覆盖子串 https://leetcode-cn.com/problems/minimum-window-substring/

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

解：

可以用滑动窗口技巧，left 和 right 指针都初始化为0，然后 right 向右滑动直到 s[left, …, right] 中包括了T串中所有的字符，就得到一个可能的解，再令 left 右滑收紧窗口直到不能满足包括T串所有字符。

from collections import Counter

class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ''

    dict\_t = Counter(t)  
    required = len(dict\_t)  # 一共需要满足条件的字符数  
    l, r = 0, 0  
    formed = 0  # window中已经满足条件的字符数  
    window = {}  
    ans = float("inf"), None, None   # (window length, left, right)

    while r < len(s):  
        char = s\[r\]  
        window\[char\] = window.get(char, 0) + 1  
        if char in dict\_t and window\[char\] == dict\_t\[char\]:  
            formed += 1

        while l <= r and formed == required:  # 满足的window，记录结果后，需要右移left  
            char = s\[l\]  
            if r-l+1 < ans\[0\]:  
                ans = (r-l+1, l, r)  
            window\[char\] -= 1  
            if char in dict\_t and window\[char\] < dict\_t\[char\]:  
                formed -= 1  
            l += 1  
        r += 1  
    return '' if ans\[0\] == float("inf") else s\[ans\[1\]: ans\[2\]+1\]

438.找到字符串中所有字母异位词 https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

解：

依然是滑动窗口的思路，只不过现在窗口中进哈希表的元素，必须在模式串中（这样比较方便）。最大的差别还是在，既要满足所有模式串中的key的value都相等（多一个少一个都不行），窗口长度又必须等于模式串长度。

from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if not s:
return []

    dict\_p = Counter(p)  
    required = len(dict\_p)  
    l, r = 0, 0  
    formed = 0  
    window = {}  
    res = \[\]

    while r < len(s):  
        char = s\[r\]  
        if char in dict\_p:  
            window\[char\] = window.get(char, 0) + 1  
            if window\[char\] == dict\_p\[char\]:  
                formed += 1

        while l <= r and formed == required:  
            if r - l + 1 == len(p):  
                res.append(l)

            char = s\[l\]  
            if char in dict\_p:  
                window\[char\] -= 1  
                if window\[char\] < dict\_p\[char\]:  
                    formed -= 1  
            l += 1  
        r += 1

    return res

189. 旋转数组 https://leetcode-cn.com/problems/rotate-array/

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

要求使用空间复杂度为 O(1) 的 原地 算法。

解：

如果空间复杂度可以是O(n)的话，先把数组转成环形链表，然后把第n-k个节点的next断开，以第n-k+1个节点开始往后扫一边，得到数组。

暴力，先想一下k=1的情况，把最后一个拿出来，然后依次后移。插k次就行了，O(kN)，超时。

class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or k == 0:
return
for _ in range(k):
tmp = nums[-1]
for i in range(len(nums)-1, 0, -1):
nums[i] = nums[i-1]
nums[0] = tmp
return

# python 中用列表是动态数组，可以通过
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or k == 0:
return
n = len(nums)
k = k % n # 先 mod n 一下，避免k大于n
for _ in range(k):
nums.insert(0, nums.pop())

# 再来一个python独享的moment，直接用列表切片来操作
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or k == 0:
return
n = len(nums)
k = k % n # 先 mod n 一下，避免k大于n

    nums\[:\] = nums\[-k:\] + nums\[:-k\]　　

如果重复做k次超时，干脆一步到位，直接把元素放到对应位置，O(N)

class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or k == 0:
return
n = len(nums)
k = k % n # 先 mod n 一下，避免k大于n

    step = 0

    start = 0  
    while step < n:  
        cur = start  
        prev\_val = nums\[start\]  # 第一个要跳的数

        while True:  # 没有回到开始的点的话就一直跳数即可  
            nex = (cur + k) % n  
            tmp = nums\[nex\]  # 暂存被跳过来的数占位置的数  
            nums\[nex\] = prev\_val

            prev\_val = tmp  # tmp是下一个要跳位置的数  
            step += 1  # 统计已经移动了多少个数  
            cur = nex  # 更新游标cur  
            if cur == start:  
                break

        start += 1  
    return

最简单直接的解法，把数组两部分分别反转，然后再整个数组反转一次。类似于谷歌面试题，一句话：A cycle of boom and bust. 倒装成：bust and boom of cycle A. 原地倒装，不允许使用额外存储空间。先全部反转，然后每个单词分别反转即可。

# python 超精简操作
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or k == 0:
return
n = len(nums)
k = k % n # 先 mod n 一下，避免k大于n

    nums\[-k:\] = nums\[-k:\]\[::-1\]  
    nums\[:-k\] = nums\[:-k\]\[::-1\]  
    nums\[:\] = nums\[::-1\]

# 写一下原地交换
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or k == 0:
return
n = len(nums)
k = k % n # 先 mod n 一下，避免k大于n

    self.helper(nums, 0, n-1)  
    self.helper(nums, 0, k-1)  
    self.helper(nums, k, n-1)

def helper(self, nums, start, end):  
    if start >= end:  
        return  
    nums\[start\], nums\[end\] = nums\[end\], nums\[start\]  
    self.helper(nums, start+1, end-1)

# 直接用迭代可能会快一点
def helper(self, nums, start, end):
if start >= end:
return
mid = start + (end-start)//2
for i in range(start, mid + 1):
nums[i], nums[end-(i-start)] = nums[end-(i-start)], nums[i]

206. 反转链表 https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解：

迭代实现，从第二个节点开始头插，反转整个链表。或者换个思路，只需要把每个指针的指向调转一下即可。

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
pre = head
p = head.next
while p: # 头插
pre.next = p.next
p.next = head
head = p
p = pre.next

    return head

# 按照简单调转指针的思路，把代码精简一下

Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev

递归实现

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
reverse_head = self.reverseList(head.next)
# 此时 head 指向reverse_head链的尾节点
head.next.next = head
head.next = None
return reverse_head

141. 环形链表  https://leetcode-cn.com/problems/linked-list-cycle/

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

解：

设置一个比如1s的时间限制，硬解，如果没有遍历到链尾，说明有环（权当开拓一下思路。。。。）

哈希集合存已经遍历过的节点，对新节点进行 O(1) 复杂度判重，空间换时间

# Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None or head.next is None:
return False
hashset = set()
p = head

    while p:  
        if p in hashset:  
            return True  
        else:  
            hashset.add(p)  
            p = p.next  
    return False

快慢指针，如果相遇说明有环，记录相遇位置。从头节点和相遇点同速度向后遍历，相遇点即为环入口。

# Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None or head.next is None:
return False
slow = head
quick = head
while quick and quick.next:
slow = slow.next
quick = quick.next.next
if slow is quick:
return True
return False

24. 两两交换链表中的节点  https://leetcode-cn.com/problems/swap-nodes-in-pairs/

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

解：

迭代实现，需要一个pre始终指向新链表的head，游标指向每两个一组的前驱，向后遍历并两两交换

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head

    pre = ListNode(0)  
    pre.next = head  
    p = pre  
    while p.next and p.next.next:  
        tmp = p.next  
        p.next = tmp.next  
        tmp.next = tmp.next.next  
        p.next.next = tmp  # 交换 p.next 和p.next.next

        p = tmp  # 下一组两个的前驱

    return pre.next

递归实现

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
# 递归，先把head开始的两个之后的链表处理完, head指向子链表的头节点，head.next指向head，head.next为新的头节点
p = head.next
head.next = self.swapPairs(p.next)
p.next = head
return p

142. 环形链表 https://leetcode-cn.com/problems/linked-list-cycle-ii/

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

解：

基本和 #141 的两种思路一致，找到环入口即可。

# Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return None
visited = set() # hashset
p = head
while p:
if p in visited:
return p
visited.add(p)
p = p.next
return None

# Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return None
intersect = self.getIntersect(head)
if not intersect:
return None
p1 = head
p2 = intersect
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1

def getIntersect(self, head):  
    if head is None or head.next is None:  
        return None  
    slow = head  
    quick = head  
    while quick and quick.next:  
        slow = slow.next  
        quick = quick.next.next  
        if slow is quick:  
            return slow  
    return None

25. K个一组翻转链表 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解：

迭代实现，每K个一组，尾插法实现翻转，如果一组不够K个就不用操作

# Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or head.next is None or k<=1:
return head
p = ListNode(0)
p.next = head # p始终指向链表头节点
pre = p
tail = p # pre, tail 都指向第一组的head

    while True:  
        count = k  
        while count and tail:  
            count -= 1  
            tail = tail.next  # 如果剩余节点超过k，tail应指向这一组第k位置节点

        if not tail:  # 如果剩余节点不足k，tail为空，不需要翻转  
            break

        # 翻转；尾插法，始终插到tail后面  
        head = pre.next  # 当前组原本的头节点  
        while pre.next != tail:  # 只要pre（前一组最后一个）没指向当前组第k位置节点，一直尾插  
            cur = pre.next  
            pre.next = cur.next # 把要尾插的节点拿掉  
            cur.next = tail.next  # 尾插  
            tail.next = cur 

        pre = head  # pre 和 tail 都指向下一组的第一个节点  
        tail = head  
    return p.next

迭代实现，用栈实现翻转

# Definition for singly-linked list.

class ListNode(object):

def __init__(self, x):

self.val = x

self.next = None

class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or head.next is None or k<=1:
return head
prev = ListNode(0) # 始终指向链表头节点
prev.next = head
p = prev
while True:
count = k
stack = [] # 用栈实现k个一组的翻转
tmp = head # 从这一组的head开始往后入栈，结束以后tmp为下一组的head
while count and tmp:
stack.append(tmp)
tmp = tmp.next
count -= 1

        if count:  # 链表剩下不够k个，跳出循环，上一组最后一个节点p接上这一组的head  
            p.next = head  
            break  
        # 翻转，这一组k个节点出栈，循环结束时 p 指向当前组的最后一个节点  
        while stack:  
            p.next = stack.pop()  
            p = p.next 

        p.next = tmp  # 当前组的最后一个指向下一组的head  
        head = tmp  # 更新 head 记录  
    return prev.next

21. 合并两个有序链表 https://leetcode-cn.com/problems/merge-two-sorted-lists/

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解：

双指针实现。虚拟头节点是一个比较好的技巧，能够减少复杂的边界判定。

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return None
if not l2:
return l1
if not l1:
return l2

    new\_head\_pre = ListNode(0)  # 虚拟头节点

    p1, p2, p = l1, l2, new\_head\_pre  
    while p1 and p2:  
        if p1.val < p2.val:  
            p.next = p1  
            p = p.next  
            p1 = p1.next

        else:  
            p.next = p2  
            p = p.next  
            p2 = p2.next

    if p1:  # p1或p2 还剩下的话，全部链上去，否则链个None收尾  
        p.next = p1  
    elif p2:  
        p.next = p2  
    else:  
        p.next = None

    return new\_head\_pre.next

递归实现，非常简洁。merge函数会返回合并好的给定两个有序链表。那么，只要1l更小，就拿出来，链上 merge(l1.next, l2) 的头节点；否则的话拿l2出来，链上 merge(l1, l2.next) 的头节点。

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return None
if not l2:
return l1
if not l1:
return l2

    if l1.val < l2.val:  
        l1.next = self.mergeTwoLists(l1.next, l2)  
        return l1  
    else:  
        l2.next = self.mergeTwoLists(l1, l2.next)  
        return l2

23. 合并k个排序链表 https://leetcode-cn.com/problems/merge-k-sorted-lists/

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

解：

暴力，遍历所有链表，把元素放到一个数组中，然后排序，再链成表。O(NlogN)，时间都花在排序上。

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
nodes = []
head_pre = ListNode(0)
p = head_pre

    for l in lists:  
        while l:  
            nodes.append(l.val)  
            l = l.next

    nodes.sort()  
    for val in nodes:  
        p.next = ListNode(val)  
        p = p.next  
    p.next = None  
    return head\_pre.next

每次都比较k个节点，拿出最小值链上，被链上的那个链表的指针后移，其他不动，O(kN)。用优先队列优化上述方法，维护一个小顶堆每次pop出来最小值，O(Nlogk)

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

import heapq
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
head_pre = ListNode(0)
p = head_pre
head = []

    for i in range(len(lists)):  
        if lists\[i\]:  
            heapq.heappush(head, (lists\[i\].val, i))  
            lists\[i\] = lists\[i\].next

    while head:  
        val, idx = heapq.heappop(head)  
        p.next = ListNode(val)  
        p = p.next  
        if lists\[idx\]:  
            heapq.heappush(head, (lists\[idx\].val, idx))  
            lists\[idx\] = lists\[idx\].next

    return head\_pre.next

逐一两两合并的思路。O(kN)。用分治优化逐一两两合并O(Nlogk)

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return
n = len(lists)
return self.merge(lists, 0, n-1)

def merge(self, lists, left, right):  # 合并left到right位置的链表  
    if left == right:  
        return lists\[left\]  
    mid = left + (right - left) // 2  
    l1 = self.merge(lists, left, mid)  # 先合并 left到mid  
    l2 = self.merge(lists, mid+1, right)  # 再合并mid+1到right  
    return self.mergeTwoLists(l1, l2)  # 把左右两个合并好的链表合并起来

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:  
    if not l1 and not l2:  
        return None  
    if not l2:  
        return l1  
    if not l1:  
        return l2

    if l1.val < l2.val:  
        l1.next = self.mergeTwoLists(l1.next, l2)  
        return l1  
    else:  
        l2.next = self.mergeTwoLists(l1, l2.next)  
        return l2

2. 两数相加 https://leetcode-cn.com/problems/add-two-numbers/

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解：

从后向前双指针模拟加法，需要注意的是，即使两个链表都遍历到最后了，也有可能出现相加后最高位进位的情况，新链表还是要再链一次。要考虑全面

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return ListNode(0)
p1, p2 = l1, l2
head_pre = ListNode(0)
p = head_pre
nex = 0
while p1 or p2 or nex:
tmp = nex
if p1:
tmp += p1.val
p1 = p1.next
if p2:
tmp += p2.val
p2 = p2.next
cur = tmp % 10
nex = tmp // 10
p.next = ListNode(cur)
p = p.next
p.next = None
return head_pre.next

考虑把两个的链表表示的数表示整型，相加后再链成表。相当于要遍历两边。

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return ListNode(0)
p1, p2 = l1, l2
head_pre = ListNode(0)
p = head_pre
value1, value2 = 0, 0
i = 1
while p1 or p2:
if p1:
value1 += p1.val*i
p1 = p1.next
if p2:
value2 += p2.val*i
p2 = p2.next
i *= 10
res = value1 + value2
if res == 0:
return ListNode(0)
while res:
p.next = ListNode(res % 10)
p = p.next
res //= 10
return head_pre.next

如果链表中的数字不是按逆序存储的呢？例如：(3→4→2)+(4→6→5)=8→0→7。用递归。

11. 盛水最多的容器 https://leetcode-cn.com/problems/container-with-most-water/

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

解：

暴力迭代，O(n2)，超时

class Solution:
def maxArea(self, height: List[int]) -> int:
if len(height) < 2:
return 0
n = len(height)
res = 0
for i in range(n):
for j in range(i+1, n):
size = min(height[j], height[i]) * (j-i)
res = max(res, size)
return res

暴力dfs，超时。由于没有重叠子问题，记忆化的dfs也不能加速。

class Solution:
def maxArea(self, height: List[int]) -> int:
if len(height) < 2:
return 0

    n = len(height)  
    res = 0

    def helper(start):  
        nonlocal res  
        if start == n:  
            return  
        for end in range(start+1, n):  
            size = min(height\[end\], height\[start\]) \* (end-start)  
            res = max(res, size)  
            helper(start+1)

    helper(0)  
    return res

双指针，左右指针往中间收紧，长度减小造成容量减小，只有取到更长的高度才可能弥补

class Solution:
def maxArea(self, height: List[int]) -> int:
if len(height) < 2:
return 0

    n = len(height)  
    res = 0  
    left, right = 0, n-1  
    while left < right:  
        tmp = min(height\[left\], height\[right\])  
        res = max(res, tmp\*(right-left))  
        # 两边指针往中间收紧，只有取到更高的高度才可能弥补长度减小的损失  
        if height\[left\] < height\[right\]:  
            while left < right and height\[left\] <= tmp:  
                left += 1  
        else:  
            while left < right and height\[right\] <= tmp:  
                right -= 1  
    return res

19. 删除链表的倒数第N个节点 https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解：

两趟遍历实现，注意使用虚拟头节点的技巧，能减少很多边界条件判断

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head is None:
return head
dummy = ListNode(0)
dummy.next = head
length = 0
p = head
while p:
length += 1
p = p.next

    length -= n  
    p = dummy  
    while length > 0:  
        length -= 1  
        p = p.next

    p.next = p.next.next  
    return dummy.next

双指针一趟遍历实现，第一个指针向前移动n+1步，第二个指针从开头出发，现在这两个指针被n个节点分开，同时移动这两个指针保持间隔，第一个指针到达尾节点，第二个指针到达倒数第n个节点。

继续使用虚拟头节点技巧，从dummy出发，第一个指针移动到Null，第二个指针移动到的p的下一个即为待删节点

# Definition for singly-linked list.

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head is None:
return head
dummy = ListNode(0)
dummy.next = head
length = n + 1
p1, p2 = dummy, dummy
while length > 0:
length -= 1
p1 = p1.next
while p1:
p1 = p1.next
p2 = p2.next
p2.next = p2.next.next
return dummy.next

31. 下一个排列 https://leetcode-cn.com/problems/next-permutation/

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解：

字典序中下一个更大的排列：

　　先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在就翻转整个数组

　　再找出另一个最大索引 l 满足 nums[l] > nums[k]

　　交换 nums[l] 和 nums[k]

　　最后翻转nums[k+1:]

class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums:
return
n = len(nums)
firstIndex = -1
def reverse(nums, i, j):
while i<j:
nums[j], nums[i] = nums[i], nums[j]
i += 1
j -= 1

    for i in range(n-2, -1, -1):  
        if nums\[i\] < nums\[i+1\]:  
            firstIndex = i  
            break  
    if firstIndex == -1:  
        reverse(nums, 0, n-1)  
        return  
    secondIndex = -1  
    for i in range(n-1, firstIndex, -1):  
        if nums\[i\] > nums\[firstIndex\]:  
            secondIndex = i  
            break  
    nums\[firstIndex\], nums\[secondIndex\] = nums\[secondIndex\], nums\[firstIndex\]  
    reverse(nums, firstIndex+1, n-1)