141. 环形链表

利用快慢指针，一开始都指到头结点处，然后每次快指针走两步，慢指针。若最后相遇了，说明有环

# 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
        """
        slow=head
        fast=head
        while fast!=None and fast.next!=None:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                return True
        return False

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow=head;
        ListNode *fast=head;
        while(fast!=nullptr && fast->next != nullptr){
            slow=slow->next;
            fast=fast->next->next;
            if (slow==fast){
                return true;
            }
        }
        return false;
    }
};

142. 环形链表 II

返回入环的第一个链表

快慢指针相遇后，把任意一个指针指向头结点，然后两个指针同速前进，当他们再次相遇时，即是入环口

# 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
      while fast!=None and fast.next!=None:
          slow=slow.next
          fast=fast.next.next
          if slow==fast:
              break
      else: return None
      slow=head
      while slow!=fast:
          slow=slow.next
          fast=fast.next
      return slow

倒数第k个节点

让快指针先走k步，然后快慢指针一起同步走。快指针到达终点时，慢指针指向的就是倒数第k个节点

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def kthToLast(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: int
        """
        fast,slow=head,head
        while k: #相当于 while k>0
            fast=fast.next
            k-=1
        while fast: # 相当于while fast!=None
            fast=fast.next
            slow=slow.next
        return slow.val

167. 两数之和2

只要数组有序，就应该想到双指针技巧

类似于二分查找，通过调节左右指针，得到目标和

class Solution(object):
  def twoSum(self, nums, target):
      left=0
      right=len(nums)-1
      while left<right:
          if nums[left]+nums[right]>target:
              right-=1
          elif nums[left]+nums[right]<target:
              left+=1
          elif nums[left]+nums[right]==target:
              return [left+1,right+1]
      else:
          return [-1,-1]

1. 两数之和1（无序）

遍历过程中，利用字典保存值对应的下标。若找到目标和，则返回下标

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
    # def two_sum(nums,target):
        dic=dict()
        for i,v in enumerate(nums):
            if target-v  in dic:
                return i, dic[target-v]
            dic[v]=i  
        # for i,j in enumerate(nums):
        #     if target-j in nums[i+1:]:
        #         return i, i+1+nums[i+1:].index(target-j)

344. 反转字符串

利用同步赋值，交换左右指针对应的值

class Solution(object):
  def reverseString(self, s):
      """
      :type s: List[str]
      :rtype: None Do not return anything, modify s in-place instead.
      """
      left=0
      right=len(s)-1
      while left<right:
          s[left],s[right]=s[right],s[left]
          left+=1
          right-=1
      return s