删除单向链表元素
- 双指针pre,cur遍历
- 注意需要特殊判断 如果删除的是head，直接返回head.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
cur = head
if cur.val == val:
# 要删除head
return cur.next
else:
while cur.next:
pre = cur
cur = cur.next
if cur.val == val:
pre.next = cur.next
return head
链表中倒数第 k 个节点
- 两个指针 latter former
- former先向前走k个节点，保持两指针之间的间距为k
- 两指针一期循环向前，直到former == null， return latter
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
former,latter = head, head
for i in range(k):
former = former.next
while former:
latter = latter.next
former = former.next
return latter
合并两个有序链表
- 造一个伪头节点（新链表）
- 循环合并
Python 三元表达式写法：A if x else B (cur.next = l1 if l1 else l2)
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 创造伪头节点，并且current指向它
fake = cur = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
# l1加到当前新链表尾部
cur.next = l1
# l1指针前进
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
# current指针前进
cur = cur.next
# 如果l1或l2还剩余，直接加到尾部
if l1:
cur.next = l1
else:
cur.next = l2
return fake.next
两个链表的第一个公共节点
- 指针1从Ahead开始遍历，结束后从Bhead再遍历
- 指针2 从Bhead开始遍历，结束后从Ahead再遍历
- 若两个指针相遇（指针1 == 指针2），即为相交node
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
A, B = headA, headB
while A != B:
A = A.next if A else headB
# 如果A结束了，去headB
B = B.next if B else headA
return A
调整数组顺序使奇数位于偶数前面
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
- 使用双指针，left/right，从两端分别去找第一个偶数和最后一个奇数
- 交换，使奇数在偶数前面
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
left,right = 0,len(nums)-1
while left<right:
# 前偶后奇，换位
if nums[left] & 1 == 0 and nums[right] & 1 == 1:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
if nums[left] & 1 == 1:
# 当前left指针指向奇数，不用换位，继续向后
left += 1
if nums[right] & 1 == 0:
# 当前right指针指向偶数，不用换为，继续向前
right -= 1
return nums
- 使用队列的 leftappend, append一层遍历完成
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
queue = collections.deque()
for num in nums:
queue.appendleft(num) if num % 2 ==1 else queue.append(num)
return list(queue)
和为 s 的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
- 由于数组是递增的，可以使用双指针的方法空间复杂度O(1)
- i从左到右，j从右到左，如果当前和>s，j--；如果当前和<s,i++；
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i,j = 0,len(nums)-1
while i<j:
sum = nums[i] + nums[j]
if sum == target:
return [nums[i],nums[j]]
elif sum < target:
i += 1
elif sum > target:
j -= 1
翻转单词顺序
输入: "the sky is blue"
输出: "blue is sky the"
- 双指针，从后向前遍历，记录单词的左右边界i,j
- 确定边界后，截取单词放到result
- 一个while大循环中，需要考虑 1.非空格的字母 2.剔除空格 3.更新单词末尾index-j
class Solution:
def reverseWords(self, s: str) -> str:
s = s.strip() #去掉两端空格
i = j = len(s) - 1
result = []
while i >= 0:
# 如果不为空格，继续往下遍历
while i >=0 and s[i] != ' ':
i -= 1
# 搜到了首个空格，把单词加进去
result.append(s[i + 1: j + 1])
# 跳过空格
while i >=0 and s[i] == ' ':
i -= 1
# 结束了一个单词的添加，改一下单词结尾j
j = i
return " ".join(result)
