1.只出现一次的数字

异或运算满足交换律 a⊕b=b⊕a ，即以上运算结果与 nums 的元素顺序无关。代码如下：

class Solution {
    public int singleNumber(int[] nums) {
        int ans =0;
        for(int num:nums){
            ans^=num;
        }
        return ans;


    }
}

 2.只出现一次的数字II

这是今天滴滴的原题，要求时间复杂度为O(1)和空间复杂度为O(n) 

方法一：哈希表

思路与算法

我们可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。

在统计完成后，我们遍历哈希映射即可找出只出现一次的元素。

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> freg =new HashMap<Integer,Integer>();
        for(int num:nums){
            freg.put(num,freg.getOrDefault(num,0)+1);
        }
        int ans =0;
        for(Map.Entry<Integer,Integer> entry:freg.entrySet()){
            int num =entry.getKey(),occ=entry.getValue();
            if(occ==1){
                ans =num;
                break;
            }
        }
        return ans;

    }
}

这个方法的效率显然不高，我们换一个思路试试看,而且时间复杂度不为O(1)

解法二：

如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

3.随机链表复制

解题思路：

// Definition for a Node.
class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

 本题链表的节点定义如下：

// Definition for a Node.
class Node {
    int val;
    Node next, random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

给定链表的头节点 head ，复制普通链表很简单，只需遍历链表，每轮建立新节点 + 构建前驱节点 pre 和当前节点 node 的引用指向即可。

本题链表的节点新增了 random 指针，指向链表中的 任意节点 或者 null 。这个 random 指针意味着在复制过程中，除了构建前驱节点和当前节点的引用指向 pre.next ，还要构建前驱节点和其随机节点的引用指向 pre.random 。

本题难点： 在复制链表的过程中构建新链表各节点的 random 引用指向。

class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Node dum = new Node(0), pre = dum;
        while(cur != null) {
            Node node = new Node(cur.val); // 复制节点 cur
            pre.next = node;               // 新链表的 前驱节点 -> 当前节点
            // pre.random = "???";         // 新链表的 「 前驱节点 -> 当前节点 」 无法确定
            cur = cur.next;                // 遍历下一节点
            pre = node;                    // 保存当前新节点
        }
        return dum.next;
    }
}

 可以对上面经典的复制链表的办法来解决这个问题

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}

4.重排链表

 先了解怎么反转链表

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路分析:

对于题目给出的链表，简化如下：

class Solution {
    public void reorderList(ListNode head) {
        ListNode prev=null;
        ListNode cur =head;
        while(cur!=null){
            ListNode nextNode =cur.next;
            cur.next=prev;
            prev=cur;
            cur=nextNode;
        }
        return prev;

    }
}

还有一个关键步骤，求出链表的中间节点 ：

题目要求的是如果有两个中间节点，则返回第二个中间节点。因此，对于该题目而言，快指针fast向前移动的条件是：fast!=null && fast.next != null。

 

 下面是完整解法：

完整代码 ：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public void reorderList(ListNode head) {
    if (head == null) {
        return;
    }

    // 获得中间节点
    ListNode mid = findMid(head);

    // 中间节点之后的部分进行反转
    ListNode head2 = mid.next;
    mid.next = null;
    head2 = reverseList(head2);

    // 合并
    ListNode head1 = head;
    mergeList(head1, head2);
}

// LeetCode 876
private ListNode findMid(ListNode head){
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast= fast.next.next;
    }
    return slow;
}

// LeetCode 206
private ListNode reverseList(ListNode head){
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode nextNode = cur.next;
        cur.next = prev;
        prev =cur;
        cur = nextNode;
    }
    return prev;
}


private void mergeList(ListNode head1, ListNode head2) {
    ListNode next1 = null;
    ListNode next2 = null;
    while (head1 != null && head2 != null) {
        next1 = head1.next;
        next2 = head2.next;

        head1.next = head2;
        head1 = next1;

        head2.next = head1;
        head2 = next2;
    }
}