数据结构与算法学习（十）

1、判断链表是否有环

1.1、题目介绍

题目来自于 LeetCode 第141题，题目介绍如下：

1.2、解题思路

使用快慢指针来解决这道问题，让快慢指针从链表头部节点开始，然后快指针每次走两步，慢指针每次走一步，如果链表有环，那么最后快慢指针一定会相遇。
注意：在编写循环判断条件的时候要保证快指针的下一步和下下一步都不能为空，否则会报空指针异常！

1.3、代码实现

ListNode定义如下

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

解题代码如下

public boolean hasCycle(ListNode head) {
    // 如果链表中一个节点都没有，直接返回false
    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、解题思路

这道题有多种解答思路，下面一一介绍

使用快速排序 + 挑选中间数的方法解答

由于要寻找的数的出现次数超过数组个数一半，那么在排好序之后，数组中间下标的那个数一定就是我们要寻找的数。
我们可以使用 快速排序 来对数组进行排序处理。

使用 HashMap 解决

用一个哈希表保存数组中的所有数据，以数组值为键，出现次数为值，将数组中各元素出现次数放入哈希表中，最后遍历哈希表即可。

2.3、解题代码

快排

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) {
        // 在pivot值左边，找到一个比pivot大的数
        while(arr[l] < pivot) {
            l += 1;
        }
        // 在pivot值右边，找到一个比pivot小的数
        while(arr[r] > pivot) {
            r -= 1;
        }
        // 如果 l 不小于 r ，退出循环
        if(l >= r) {
            break;
        }
        //交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        // 如果交换后arr[l] == pivot
        //那么让 r -= 1
        if(pivot == arr[l]) {
            r -= 1;
        }
        if(pivot == arr[r]) {
            l += 1;
        }
    }
    // 如果l==r，那么让l+=1，r-=1，避免栈溢出
    if(l == r) {
        l += 1;
        r -= 1;
    }
    //递归
    if(l < right) {
        quickSort(arr,l,right);
    }
    if(r > left) {
        quickSort(arr,left,r);
    }
}

哈希表

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种
        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;
}