526互联

环形链表_相交链表_多数元素（java语言）

发布时间 2023-04-15 09:59:38作者: 蜀道，难

环形链表

力扣141题

问题：

image-20230415094450256

image-20230412110532236

image-20230412110543854

思路：创建hashset，把链表的每个节点放到集合中，在放入的过程中检查这个节点是否已经存在，存在则证明存在环。

代码实现：

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            if (set.contains(head))
                return true;
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

相交链表

力扣160题

问题：

image-20230412111252665

image-20230412111307718

思路：先把其中一个链表的结点都放到一个hashset中，然后检索hashset，看是否包含这个节点，如果包含，则证明这个节点就是开始相交的节点，输出答案。

代码实现：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode temp = headA;//头指针不方便移动，赋值给temp
        while (temp != null){
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null){
            if (set.contains(temp))//如果保护这个节点，则直接返回这个节点。
                return temp;
            temp = temp.next;
        }
        return null;
    }
}

多数元素

力扣169题

问题：

image-20230415093459065

思路：数组中元素出现的次数很容易让人想到hashmap,所以把数组中每个出现的数字以及它们出现的次数放入到hashmap,然后遍历hashmap，判断哪个数字出现的次数大于nums.length / 2,是的话就把这个数字输出。

代码实现：

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        //把数组中的每个数字和对应出现的次数存放到map中
        for(Integer i : nums){
            Integer count = map.get(i);
            count = count == null ? 1 : ++count;
            map.put(i,count);
        }
        //把数组中
        for(Integer i : map.keySet()){
            Integer count = map.get(i);
            if (count > nums.length / 2)
                return i;
        }
        return 0;
    }
}