例一.27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
#双指针法（快慢指针）
#
slowinx=0
fastinx=0
n=len(nums)
while fastinx<=n-1:
if nums[fastinx]!=val:
nums[slowinx]=nums[fastinx]
slowinx+=1
fastinx+=1
return slowinx
#暴力解法
#此解法的难点在于循环次数是个变量，即数组的长度在变
#每次移动数组都要把尾部的冗余数剔除
#python:for循环range中不允许有变量
n=len(nums)
i=0
while i<=n-1:
if nums[i]==val:
for j in range(i+1,n):
nums[j-1]=nums[j]
i-=1 #因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
n-=1 # 此时数组的大小-1
i+=1
return n
例二.977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
class Solution(object):
def sortedSquares(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
#暴力
n=len(nums)
tmp=[]
for i in range(n):
tmp.append(nums[i]*nums[i])
tmp.sort()
return tmp
#双指针
#首位双指针
n=len(nums)
tmp=[]
left,right=0,n-1
while left<=right:
if nums[left]<0: #当数组中存在负数
if -nums[left]>nums[right]:
tmp.append(nums[left]*nums[left])
left+=1
else: #当数组中都是正数
tmp.append(nums[right]*nums[right])
right-=1
else:
tmp.append(nums[right]*nums[right])
right-=1
# print(tmp)
tmp.reverse() #也可以先声明一个n长的tmp一维数组，再从后往前填数，就不用reverse了
return tmp
例三.209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
#滑动窗口
#重点：需要弄清滑动窗口的机制，什么时候左边指针动，什么时候右边指针动
#while addnums>=target: left+=1
#当走出while addnums>=target: 右指针动
n=len(nums)
left=0
res=[]
addnums=0
cnt=0
for right in range(n):
addnums+=nums[right]
# right+=1
cnt+=1
while addnums>=target:
res.append(cnt)
# print(res)
cnt-=1
addnums-=nums[left]
left+=1
if res:
return min(res)
return 0
#暴力解法(超出时间限制)
n=len(nums)
res=[]
for i in range(n):
addnums=0
cnt=0
for j in range(i,n):
cnt+=1
addnums+=nums[j]
if addnums>=target:
res.append(cnt)
break
if res:
return min(res)
return 0
例四.344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
#双指针法
n=len(s)
left,right=0,n-1
tmp=""
while left<right:
tmp=s[left]
s[left]=s[right]
s[right]=tmp
left+=1
right-=1
return s
#调库函数 考试时不推荐使用
# s.reverse()
# return s
例五.541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
# s="abcdefg"
# k=8
# 双指针法
s=list(s)
n=len(s)
left0,right0=0,k-1 #left 和right各自的初始位置
while left0<n-1:
left,right=left0,right0 #初始化left,right
leng=len(s[left0:n]) #单独处理剩余部分
if leng<k: #剩余字符少于 k 个，剩余全部反转
right=n-1
#剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符,正常程序处理即可
tmp=""
while left<right:
tmp=s[left]
s[left]=s[right]
s[right]=tmp
left+=1
right-=1
left0+=2*k #按要求翻转后初始位置+=2*k
right0+=2*k
return "".join(s)
#同样的方法，但把翻转部分写成函数
def reverse_substring(text):
left, right = 0, len(text) - 1
while left < right:
text[left], text[right] = text[right], text[left]
left += 1
right -= 1
return text
res = list(s)
for cur in range(0, len(s), 2 * k): #从头到尾步长2k
res[cur: cur + k] = reverse_substring(res[cur: cur + k]) #前k个翻转
return ''.join(res)
例六.206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
#递归法
def dfs(pre,curNode):
if not curNode:
return pre #curNode=None时，进行最后的返回
nextNode=curNode.next #保存下一节点
curNode.next=pre #翻转
return dfs(curNode,nextNode) #进行下一步
return dfs(None,head) #返回的pre是最终结果
#双指针法
#别忘记尾部的None
tail=None
if not head:
return None
if not head.next:
return head
curNode=head.next
nextNode=head.next.next
head.next=tail
while curNode and nextNode:
#翻转
curNode.next=head
head=curNode
curNode=nextNode
nextNode=curNode.next
if head and curNode and not nextNode: #处理两个节点
curNode.next=head
return curNode
##简化版双指针代码
#（虽然都是双指针，这里pre = None cur = head的方式显然更简单，可以省去很多情况讨论）
cur = head
pre = None
while(cur!=None):
temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur.next = pre #反转
#更新pre、cur指针
pre = cur
cur = temp
return pre
例七.24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
思路：通过pre\cur\tmp三个指针的移动来改变链表，同时要注意当节点个数是单数时的情况，还有到了链表尾部的None时特别注意。
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
if not head.next:
return head
pre=head
cur=pre.next
res=cur
while cur:
tmp=cur.next
cur.next=pre
if not tmp or not tmp.next:
pre.next=tmp
break
pre.next=tmp.next #当tmp.next为None
pre=tmp
cur=tmp.next #当tmp为None
return res
例八.19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
#双指针+虚拟头节点
#设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了;还便于返回结果
#思路：fast先抢跑n+1步，之后slow和fast同步移动，这样slow和fast间就能有n+1的间隔
#fast到达链表尾部时，slow指向数的下一个数就是要删除的数
head_dummy=ListNode()
head_dummy.next=head
slow,fast=head_dummy,head_dummy
n+=1
while n:
fast=fast.next
n-=1
while fast:
fast=fast.next
slow=slow.next
slow.next=slow.next.next
return head_dummy.next
#直接暴力
#缺点：走了两遍链表
leng=1
head_copy=head
res=head
while head_copy.next:
leng+=1
head_copy=head_copy.next
cnt=leng-n #删除第cnt+1个节点
if cnt==0:
head=head.next
return head
while cnt>1:
head=head.next
cnt-=1
#当cnt==1 或者 cnt>1
if head.next:
head.next=head.next.next
return res
例九.面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
#快慢指针求解链表相交
#走你走过的路
headA_copy=headA
headB_copy=headB
while headA or headB:
if headA!=headB:
if headA:
headA=headA.next
else:
headA=headB_copy
if headB:
headB=headB.next
else:
headB=headA_copy
else:
return headA
if not headA and not headB:
return None
例十.142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
思路：
- 判断链表是否环：分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
- 如果有环，如何找到这个环的入口：从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
# 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
"""
slow,fast=head,head
if fast==None:
return None
if fast.next==None:
return None
fast=fast.next.next
slow=slow.next
while slow!=fast and fast and fast.next:
fast=fast.next.next
slow=slow.next
if slow==fast:
while slow!=head:
head=head.next
slow=slow.next
return slow
if fast==None or fast.next==None:
return None
