链表的算法

可以认为无论Hash表存储多少数据，增删改查的时间复杂度都是常数级别O(1)，但是常数时间比较大

如果Hash表存储是Key是基本类型比如：Interge,Double,String…那么Hash表内部传递的过程是按值传递的，在Hash表中所占的空间就是这个基本数据类型需要的空间（Hash表会拷贝一份值）

如果Key存储的不是基本类型，那么内部的传递过程是按照内存地址(引用)传递的，所占的空间一律是8字节

增删改查的时间复杂度是O(logN)

非基础类型的数在加入顺序表的时候，都需要把对应的比较器也一起传递过去

双指针

快慢指针

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        int count = 0;
        while(slow != null){
            count++;
            slow = slow.next;
        }
        if(count == 1){
            return true;
        }
        if(count == 2){
            return head.val == head.next.val;
        }
        slow = head;
        if(count % 2 == 0){
            fast = fast.next.next; // 如果是偶数个节点的话，慢指针只需要移动 count / 2 - 1次，
            while(fast != null){ // 假设有4个数(1 2 3 4)，慢指针移动到指定位置(3)只需要2次移动，而快指针移动2次的话到达了null，也就是最终fast到达了null,所以是fast != null
                fast = fast.next.next;
                slow = slow.next;
            }
        }else{
            while(fast.next != null){ // 假设有5个数字(1 2 3 4 5)，慢指针移动到指定位置(3)需要两次，而快指针移动两次到达了5，也就是最终fast.next = null，也就是fast.next != null
                fast = fast.next.next;
                slow = slow.next;
            }
        }
        ListNode last = reverse(slow);
        fast = last;
        slow = head;
        while(slow != null && fast != null){
            if(slow.val != fast.val){
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        reverse(last);
        return true;
    }
    public static ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode next = head.next;
        while(head.next != null){ // 先动 next 在动 pre 在动 head
            head.next = pre;
            pre = head;
            head = next;
            next = head.next;
        }
        head.next = pre;
        return head;
    }
}

笔试做法：把单链表每一个节点放到数组里面去，然后在数组里面利用快排的Partition,完成后重新组合为一个数组

活用链表的性质：使用六个变量，大于区域的头和尾，等于区域的头和尾，小于区域的头和尾，遍历一遍链表，把各个节点分配给各个区域的头和尾巴，最后把个个区域连接起来即可（最后连接的时候需要注意边界条件，因为三个区域可能有2个或者1个为空区域，空指针如果调用方法会报错）

要梳理一下这种逻辑

这道题一开始我还没理解，难点在于如何找到新链表节点的next指针指向的新节点和rand指针指向的新节点（可以使用HashMap）分别存储老节点和对应的克隆节点，之后依次复制就可以了

不用HashMap的方式：

每次复制的新节点，可以连接在老节点的next指针上，第一轮先把全部的节点复制完毕，之后的一轮循环用于设置新节点的rand指针，根据老节点的rand指针，我们可以找到与之对应的新节点，这个新节点就在老节点rand指针指向的节点的下一个节点，最后一轮循环，把新老节点分离组成新老链表（省去HashMap记录节点的位置，用节点本身去记录了位置信息）

首先需要判断链表是否有环

第一种方法：遍历链表的同时把遍历的节点送入HashMap,送入HashMap之前判断HashMap中是否存在这个节点，如果存在的，那么遍历结束，这个节点就是入环的第一个节点，如果遍历到最后也没有发现重复的节点，那么就不存在环(这种方法实现容易，但是额外空间复杂度较高)

第二种方法：使用快慢指针，如果有环，慢指针走的慢，快指针走的快，那么快慢指针一定会相遇（而且在环内快指针走的圈数不会超过2圈）

假设慢指针入环的时候快指针与满指针之间的距离为 L ,快指针的速度是慢指针的N倍，慢指针速度为 1，那么快指针与满指针相遇的方程为（L + T ）= N * T – > T = L / (N - 1) （在环中，L 最大是一圈，假设L取最大） 那么 快指针运动的圈数Y就是Y = N / (N - 1)[N = 2 , Y = 2, N = 3, Y = 1.5 , 当 N 取 + inf Y = 1 ]，Ymax = 2,是个常数圈，不会耗费太多时间

当快慢指针相遇后，把快指针置于头节点（把快指针速度设置为和慢指针相同），下一次快慢指针相遇的节点，一定是入环的节点。

这个结论可以通过数学证明来解释。假设链表头节点到环入口节点的距离为A，环的长度为B，快慢指针第一次相遇的位置到环入口节点的距离为C。根据快指针速度是慢指针速度的两倍，第一次相遇时，快指针在环内至少比慢指针多走了一个完整的环的长度B。

因此，我们可以得到以下公式：

慢指针走的距离：A + C
快指针走的距离：A + C + nB（n为快指针在环内走的圈数）

因为快指针速度是慢指针速度的两倍，所以快指针走的距离是慢指针走的距离的两倍，即

2(A + C) = A + C + nB

化简可得

A = (n-1)B + (B - C)

这个公式说明，链表头节点到环入口节点的距离A等于快指针多走n-1圈的长度（n为正整数），再加上慢指针和快指针在环内相遇点到环入口的距离差。

当快指针回到头节点时，慢指针在环内已经走了(n-1)圈加上(B-C)的距离。此时，快指针和慢指针的距离为A，即链表头节点到环入口节点的距离。因此，下一次快慢指针相遇的位置一定是环入口节点。

因此，通过这种方法，我们可以在O(B)的时间复杂度内找到环入口节点，其中B是环的长度。

如果两个链表都是无环链表

• 首先遍历找到两个链表的尾节点，并记录两个链表的长度，如果链表的尾节点不同，那么不相交，如果相同，那么相交，进入下一步
• 长链表先走差值步（链表长度之差），之后两个链表一起走，相遇的第一个节点就是相交节点

如果一个是有环链表，一个是无环链表，这两个链表不可能相交

如果两个都是有环链表，分为以上三种情况

如果两个入环节点相同，就是第二种情况，这种情况下可以转换为两个无环链表的方式，把入环节点看作尾节点

情况 1 3 可以抽象为一种情况，让一个入环节点继续往下，如果在回到自己的过程中遇到了另外一个入环节点，就是相交，如果没有遇到另外一个入环节点，就是不相交。

创建链表数组

/**
 *
 * @param lists 一个二维整形数组，根据二维整形数组创建链表数组
 * @return
 */
public static ListNode[] generateLists(int[][] lists){
    ListNode[] list = new ListNode[lists.length];
    for (int i = 0; i < lists.length; i++) {
        ListNode head = null;
        if(lists[i].length > 0){
            head = new ListNode(lists[i][0], null);;
        }
        ListNode tmp = head;
        for (int j = 1; j < lists[i].length; j++) {
            head.next = new ListNode(lists[i][j], null);
            head = head.next;
        }
        list[i] = tmp;
    }
    return list;
}

检查链表是否有环

/**
 * 检查链表是否有环
 * @param head 链表头节点
 * @return 有环则返回第一个环节点，无环则返回null
 */
public static ListNode isLoop(ListNode head){
    ListNode fast = head, slow = head;
    if(head == null  head.next == null){
        return null;
    }
    fast = fast.next.next;
    slow = slow.next;
    while (fast != slow){
        if(fast == null  fast.next == null){
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    fast = head;
    while (fast != slow ){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

LeetCode 合并 K 个升序链表

解法一：两个两个处理

public ListNode mergeKLists(ListNode[] lists) {
    if(lists.length == 0){
        return null;
    }
    ListNode head = lists[0];
    for (int i = 1; i < lists.length; i++){
        head = mergeTwoList(head, lists[i]);
    }
    return head;
}

public static ListNode mergeTwoList(ListNode head1, ListNode head2){
    ListNode head = new ListNode();
    ListNode tmp = head;
    while(head1 != null && head2 != null){
        tmp.next = head1.val > head2.val ? head2 : head1; 
        tmp = tmp.next;
        if(head1 == tmp){
            head1 = head1.next;
        }else{
            head2 = head2.next;
        }
    }
    if(head1 == null){
        tmp.next = head2;
    }else{
        tmp.next = head1;
    }
    return head.next;
}

解法二：优先队列

用有限队列因为底层的小根堆不具有稳定性，所以建立的链表可能成环，需要把每个节点的next指针都设置为null，避免成环

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new ListNodeComparator());
    ListNode head;
    for (int i = 0; i < lists.length; i++) {
        head = lists[i];
        while (head != null){
            queue.add(head);
            ListNode tmp = head;
            head = head.next;
            tmp.next = null;
        }
    }
    head = queue.poll();
    ListNode tmp = head;
    while (!queue.isEmpty()){
        tmp.next = queue.poll();
        tmp = tmp.next;
    }
    return head;
}

    class ListNodeComparator implements Comparator<ListNode> {

    @Override
    public int compare(ListNode t1, ListNode t2) {
        return t1.val - t2.val;
    }
}