【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加

---

🐌个人主页： 🐌 叶落闲庭
💨我的专栏：💨
c语言
数据结构
javaEE
操作系统
Redis

石可破也，而不可夺坚；丹可磨也，而不可夺赤。

---

一、只出现一次的数字

1.1 题目描述

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

---

---

1.2 思路分析

这道题可以通过使用Map集合将数组中的数字作为键存储，这个数字出现的次数作为值存储，将整个数组遍历按这个键值对的方式存储，最后再遍历这个集合判断哪个数字对应的值为1就表示这个数字只出现了一次：

• 创建Map集合，遍历数组，根据当前数字作为键的参数拿到集合中的值count，再判断这个count值是否为空，若为空，则默认这个值为1，将其和当前数字添加到Map集合中，若不为空，则这个值自增1，表示第二次出现这个数字，再将其和当前数字添加到Map集合中，覆盖之前的键值对，当遍历完这个数组后，再对Map集合进行遍历，根据数字作为键的参数得到它所出现的次数，判断这个此时是否等于1，若等于1，即表示当前数字只出现了一次，返回这个数字即可。
  巧用技巧，这道题还有一个比较简单的方式，由于数组中肯定有一个数字只出现了一次，其它数字都是成对出现的，所以可以将整个数组的数字进行按位异或，两个相同的数字异或为0,0异或任何数仍未任何数：
• 定义一个变量拿到数组的第一个元素，然后从他的下一个索引处开始遍历数组，遍历得到的数组的每一个元素都和这个值进行异或，结果再赋给这个值，遍历结束后返回这个值即可。

1.3 代码演示

• Map集合：

public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        //map集合中的键是查的数字，值是数字出现的次数
        for(Integer num : nums) {
            Integer count = map.get(num);
            count = count == null ? 1 : ++count;
            map.put(num,count);
        }

        for (Integer num : map.keySet()) {
            int count = map.get(num);
            if (count == 1) {
                return num;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 异或：

public int singleNumber(int[] nums) {
        int result = nums[0];
        if (nums.length > 1) {
            for (int i = 1; i < nums.length; i++) {
                result = result ^ nums[i];
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9

二、多数元素

2.1 题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

---

---

2.2 思路分析

与上一道题类似，也是通过使用Map集合将数组中的数字作为键存储，这个数字出现的次数作为值存储，将整个数组遍历按这个键值对的方式存储，最后再遍历这个集合判断哪个数字对应的值大于数组长度的½：

• 创建一个Map集合，遍历数组得到数组的每一个数字，根据这个数字作为map集合获取值的参数得到一个整型值赋给一个整型变量，判断这个变量的值是否存在，若不存在，则将该值默认赋值为1表示该数字出现一次，否则该数字自增1，表示该数字多次出现，遍历完数字后，就收集到了每个数字出现的次数，遍历Map集合，得到每个数字的值判断其是否大于数组长度的½，若存在这个数字，直接返回该数字即可。

2.3 代码演示

   public int majorityElement(int[] nums) {
        //利用map排序
        Map<Integer,Integer> map = new HashMap<>();
        for (Integer num : nums) {
            Integer count = map.get(num);
            count  = count == null ? 1 : ++count;
            map.put(num,count);
        }

        for (Integer num : map.keySet()) {
            int count = map.get(num);
            if (count > (nums.length/2)) {
                return num;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、环形链表 II

3.1 题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。

---

---

---

3.2 思路分析

这个算是环形链表判断的进阶版，是要返回环的入口节点所对应的索引值，我的思路还是利用快慢指针，先将入环节点找到，再定义一个新的节点指向链表的头，新节点从链表头开始与入环处节点同时遍历，当两个节点相遇时，新节点就可以作为入环节点的索引返回：

• 当链表为空或者链表的第二个节点为空时，返回空，表示没有环
• 链表不为空时，定义两个指针均指向链表头，当快指针不为空时，进入循环，此时，慢指针指向它的下一个节点，当快指针的下一个节点不为空时，快指针指向它的下一个节点的下一个节点（比慢指针多走一步），当快指针的下一个节点为空时，直接返回空（表示没有环），当快指针和慢指针相遇时，此时的快（或慢）指针即为入环节点，定义一个节点指向链表头结点，当新节点与此时的慢指针不相等时，开始循环，每次各走一步，当两个节点相遇时，新指针就是入环节点的索引，返回即可。

3.3 代码演示

public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        //定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null) {
            slow = slow.next;
            if(fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while(ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
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

四、两数相加

4.1 题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

---

---

---

4.2 思路分析

直接分析代码的逻辑，这道题的实现是将两个链表中节点的值相加，最后得到一个新的链表，新链表对应的值是两个旧链表值的和：

• 定义两个节点指针分别表示新链表的头和尾，初始时均为空，定义一个整型变量作为进位节点的值，当有链表不为空时，进入循环，定义整型变量记录非空节点的值，将两个链表的值与进位值相加得到一个总数，当新链表的头为空时，将新链表的头和尾军指向一个值为总数模10得到的余数的节点，然后更新进位值为总数除以10得到的商（向下取整），当两个链表不为空时继续遍历两个链表，进入第二次循环，记录非空链表的节点值，记录总数（两个节点值+进位值），第二次循环新链表的头不为空，则将新链表的尾的下一个节点指向一个值为总数模10得到的余数的节点，再将尾指向尾的下一个节点，更新进位值为总数除以10得到的商（向下取整），继续遍历链表，当两个链表都遍历完时，还需要判断进位值是否大于0，若大于0，则将新链表的尾的下一个节点指向值为进位值的新节点，再将为指向尾的下一个节点，最后返回新链表的头。

4.3 代码演示

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode tail = null;
        //定义进位节点值
        int carry = 0;
        //当有一个链表不为空时，进入循环
        while(l1 != null || l2 != null) {
            //记录非空链表的节点值
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            //记录总数
            int sum = n1 + n2 + carry;
            if(head == null) {
                head = tail = new ListNode(sum%10);
            } else {
                tail.next = new ListNode(sum%10);
                tail = tail.next;
            }
            //更新carry的值
            carry = sum / 10;
            //当链表不为空时，继续遍历两个链表
            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }
        if(carry > 0) {
            tail.next = new ListNode(carry);
            tail = tail.next;
        }
        return head;
    }
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

---