力扣刷题——反转字符串

344.反转字符串编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。示例 1输入s [“h”,“e”,“l”,“l”,“o”]输出[“o”,“l”,“l”,“e”,“h”]示例 2输入s [“H”,“a”,“n”,“n”,“a”,“h”]输出[“h”,“a”,“n”,“n”,“a”,“H”]提示1 s.length 105s[i] 都是 ASCII 码表中的可打印字符实现代码:# Definitionforsingly-linked list.#classListNode(object):# def__init__(self,x):# self.valx # self.nextNoneclassSolution(object):defdetectCycle(self,head)::type head:ListNode:rtype:ListNode dummyheadListNode(0,head)ifdummyhead.next is None:returnNone fastdummyhead slowdummyheadwhilefast and fast.next:fastfast.next.next slowslow.nextiffastslow:breakindex1fast index2dummyheadwhileindex1 and index2:ifindex1index2:returnindex1 index1index1.next index2index2.nextreturnNone核心思路——双指针fast每次移动两个节点slow每次移动一个节点那么如果链表存在环则两个指针一定会在环中相遇。fast每次比slow多移动一个节点就相当于slow在原地不动fast一步一步地去追slow而fast的真实移动速度是slow的两倍所以fast一定会在slow完成一圈移动之内追上。那么代码实现思路为1.判断链表是否有环2.确定环的入口在哪里根据数学推导得相遇点即为环的入口点