哆啦 C 梦

问题描述 Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list. 测试样例 12Input: head = [1,2,3,4,5], left = 2, right = 4Output: [1,4,3,2,5] 12Input: head = [5], left = 1, right = 1Output: [5] 说明 1234The number of nodes in the list is n.1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n 解题 思路 以 1 -> 2 -> 3 -> 4 -> 5 , le ...

问题描述 Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false. 测试样例 123Input: head = [3,2,0,-4], pos = 1Output: ...

问题描述 Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null. For example, the following two linked lists begin to intersect at node c1: The test cases are generated such that there are no cycles anywhere in the entire linked structure. Note that the linked lists must retain their original structure after the function returns. Custom Judge: The inputs to the judge are given as ...

问题描述 Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node. 测试样例 123Input: head = [1,2,3,4,5]Output: [3,4,5]Explanation: The middle node of the list is node 3. 123Input: head = [1,2,3,4,5,6]Output: [4,5,6]Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one. 说明 12The number of nodes in the list is in the range [1, 100].1 <= Node.val <= 100 解题 思路 使用快慢指针， ...

问题描述 Given the head of a singly linked list, reverse the list, and return the reversed list. 测试样例 12Input: head = [1,2,3,4,5]Output: [5,4,3,2,1] 12Input: head = [1,2]Output: [2,1] 12Input: head = []Output: [] 说明 12The number of nodes in the list is the range [0, 5000].-5000 <= Node.val <= 5000 解题 思路 记录 pre, curr 指针, 在遍历时记录每轮 next 指针，逆向即可。 补充： 链表 时间复杂度 O(n) 代码 1234567891011121314151617181920212223242526/** * Definition for singly-linked list. * public class ListNode { * i ...

问题描述 Given an array of integers nums, sort the array in ascending order. 测试样例 12Input: nums = [5,2,3,1]Output: [1,2,3,5]] 12Input: nums = [5,1,1,2,0,0]Output: [0,0,1,1,2,5] 说明 121 <= nums.length <= 5 * 10^4-5 * 10^4 <= nums[i] <= 5 * 10^4 解题 思路 插入排序 O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快排 O(nlogn) 归并排序 O(nlogn) 补充： 插入/冒泡/选择排序复杂度较高，会超时，这里仅实现 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737 ...

问题描述 Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head. The steps of the insertion sort algorithm: Insertion sort iterates, consuming one input element each repetition and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain. The following is a graphical example of th ...

问题描述 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). 测试样例 123Input: nums1 = [1,3], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,3] and median is 2. 123Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. 12Input: nums1 = [0,0], nums2 = [0,0]Output: 0.00000 12Input: nums1 = [], nums2 = [1]Outpu ...

问题描述 Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become: [4,5,6,7,0,1,4] if it was rotated 4 times. [0,1,4,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]]. Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array. You must decrease the ove ...

问题描述 You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Follow up: Your solution should run in O(log n) time and O(1) space. 测试样例 12Input: nums = [1,1,2,3,3,4,4,8,8]Output: 2 12Input: nums = [3,3,7,7,10,11,11]Output: 10 说明 121 <= nums.length <= 10^50 <= nums[i] <= 10^5 解题 思路 使用二分法，根据中点前后的元素个数为奇/偶数来判断目标的位置，目标必然在奇数的一侧。 注意需要判断中点是相同元素的前 ...