1、判断链表是否有环
1.1、题目介绍
题目来自于 LeetCode 第141题 ,题目介绍如下:

1.2、解题思路
使用快慢指针来解决这道问题,让快慢指针从链表头部节点开始,然后快指针每次走两步,慢指针每次走一步,如果链表有环,那么最后快慢指针一定会相遇。
注意:在编写循环判断条件的时候要保证快指针的下一步和下下一步都不能为空,否则会报空指针异常!
1.3、代码实现
ListNode
定义如下
1 2 3 4 5 6 7
| public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
|
解题代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public boolean hasCycle(ListNode head) { if(head == null) { return false; } ListNode fast = head; ListNode slow = head; while(fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; if(slow == fast) { return true; } } return false; }
|
1.4、提交结果

2、数组中出现次数超过一半的数字
2.1、题目介绍
这是 剑指Offer第39题,题目介绍如下

2.2、解题思路
这道题有多种解答思路,下面一一介绍
由于要寻找的数的出现次数超过数组个数一半,那么在排好序之后,数组中间下标的那个数一定就是我们要寻找的数。
我们可以使用 快速排序 来对数组进行排序处理。
用一个哈希表保存数组中的所有数据,以数组值为键,出现次数为值,将数组中各元素出现次数放入哈希表中,最后遍历哈希表即可。
2.3、解题代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| public int majorityElement(int[] nums) { quickSort(nums,0,nums.length - 1); return nums[(nums.length - 1) / 2]; } public static void quickSort(int[] arr,int left,int right) { int l = left; int r = right; int temp = 0; int pivot = arr[(left + right) / 2]; while(l < r) { while(arr[l] < pivot) { l += 1; } while(arr[r] > pivot) { r -= 1; } if(l >= r) { break; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; if(pivot == arr[l]) { r -= 1; } if(pivot == arr[r]) { l += 1; } } if(l == r) { l += 1; r -= 1; } if(l < right) { quickSort(arr,l,right); } if(r > left) { quickSort(arr,left,r); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer count = map.get(nums[i]); if(count == null) { count = 1; } else { count++; } map.put(nums[i],count); } for (int i = 0; i < nums.length; i++) { Integer count = map.get(nums[i]); if(count > (nums.length / 2)) { return nums[i]; } } return -1; }
|
2.4、提交结果
