相交链表

总会相等的，要么在相交节点，要么在

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int count = 0;
        while (curA != curB){
            //这里为什么可以两个都为null从而退出呢？这是因为这里为null的逻辑啊，他们其实还有一个null节点
            curA = curA == null ? headB:curA.next;
            curB = curB == null ? headA:curB.next;
        }
        return curA;
    }
}

反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

回文链表

拿到链表的解法（这里用linkedlist会超时）

class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        int left = 0;
        int right = list.size()-1;
        while (left < right){
            if(list.get(left) != list.get(right))return false;
            left++;
            right--;
        }
        return true;
    }
}

空间为O(1)的解法

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode index = middle(head);
        ListNode head1 = reverse(index);
        ListNode cur = head;
        ListNode cur1 = head1;
        while (cur != index){
            if(cur.val != cur1.val)return false;
            cur = cur.next;
            cur1 = cur1.next;
        }
        return true;

    }
    public ListNode middle(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

}

环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)return true;
        }
        return false;

    }
}

环形链表Ⅱ

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode res = head;
                while (res != slow){
                    res = res.next;
                    slow = slow.next;
                }
                return res;
            }
        }
        return null;
    }
}

拼接两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode res = new ListNode();
        ListNode cur3 = res;
        while (cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur3.next = cur1;
                cur1 = cur1.next;
            }else{
                cur3.next = cur2;
                cur2 = cur2.next;
            }
            cur3 = cur3.next;
        }
        if(cur1 == null){
            cur3.next = cur2;
        }else {
            cur3.next = cur1;
        }
        return res.next;
    }
}

两数相加

会超过int的范围

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        int carry = 0;
        //当l1,l2都为空，并且没有进位时，就是结束了。
        while (l1 != null || l2 != null || carry != 0){
            //有值就按值来，没有就按0来
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;

            //计算当前位置上的数
            int sum = val1+val2+carry;
            //看下一个进位是多少
            carry = sum/10;
            //确定该节点上的数
            cur.next = new ListNode(sum%10);
            //遍历
            cur = cur.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

删除链表的倒数第n个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode front = dummy;
        for(int i = 0;i <= n;i++){
            front = front.next;
        }
        ListNode behind = dummy;
        while (front != null){
            front = front.next;
            behind = behind.next;
        }
        behind.next = behind.next.next;
        return dummy.next;
        
    }
}

两两交换链表的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode node1 = dummy;
        while (node1.next != null && node1.next.next != null){
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;
            ListNode node4 = node3.next;
            node1.next = node3;
            node3.next = node2;
            node2.next = node4;
            node1 = node2;
        }
        return dummy.next;
    }
}

k个一组翻转链表

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0,head);

        ListNode count = head;
        int sum = 0;
        while (count != null){
            sum++;
            count = count.next;
        }

        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode cur = head;
        while (sum >= k){
            sum -= k;
            for(int i = 0;i < k;i++){
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            ListNode tmp1 = p0.next;
            p0.next = pre;
            tmp1.next = cur;
            p0 = tmp1;

        }
        return dummy.next;
    }
}

随机链表的复制

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        HashMap<Node,Node> hashMap = new HashMap<>();
        while(cur != null){
            hashMap.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).random = hashMap.get(cur.random);
            cur = cur.next;
        }
        return hashMap.get(head);
    }
}

排序链表

class Solution {
    public ListNode sortList(ListNode head) {
        //没有节点和节点为1都不用排序，直接返回
        if(head == null || head.next == null){
            return head;
        }
        //找到中间节点
        ListNode head2 = middle(head);
        //这里会一层层递归下去，直到变成点
        head = sortList(head);
        head2 = sortList(head2);
        //然后合并
        return merge(head,head2);

    }
    //这里不仅仅只找到中间节点
    public ListNode middle(ListNode head){
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        return slow;
    }
    public ListNode merge(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1:list2;
        return dummy.next;
    }
}

合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int m = lists.length;
        if(m == 0){
            return null;
        }
        for (int step = 1;step < m;step *= 2){
            for(int i = 0;i < m-step;i += step*2){
                lists[i] = merge(lists[i],lists[i+step]);
            }
        }
        return lists[0];
    }
    public ListNode merge(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1:list2;
        return dummy.next;
    }
}

LRU

class LRUCache {
    public static class Node {
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int K, int V) {
            this.key = K;
            this.value = V;
        }
    }

    private HashMap<Integer, Node> keyToValue;
    private final Node dummy; // 虚拟头尾节点
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.keyToValue = new HashMap<>(capacity);
        this.dummy = new Node(0, 0);
        dummy.next = dummy;
        dummy.pre = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }

    public void put(int key, int value) {
        if (keyToValue.containsKey(key)) {
            Node node = getNode(key);
            node.value = value;
        } else {
            Node node = new Node(key, value);
            keyToValue.put(key, node);
            putFront(node);
            // 如果超过容量，移除最久未使用的节点
            if (keyToValue.size() > capacity) {
                Node lastNode = dummy.pre;
                remove(lastNode);
                keyToValue.remove(lastNode.key); // 必须从 HashMap 中删除！
            }
        }
    }

    private Node getNode(int key) {
        if (!keyToValue.containsKey(key)) {
            return null;
        }
        Node node = keyToValue.get(key);
        remove(node); // 先从链表中移除
        putFront(node); // 再放到链表头部
        return node;
    }

    private void remove(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
    }

    private void putFront(Node node) {
        Node oldHead = dummy.next;
        dummy.next = node;
        node.pre = dummy;
        node.next = oldHead;
        oldHead.pre = node;
    }
}

class LRUCache {
    class Node{
        Node pre;
        Node next;
        int val;
        int key;
        public Node(int K,int V){
            key = K;
            val = V;
        }
    }

    HashMap<Integer,Node> keyToValue;
    private int capacity;
    private Node dummy = new Node(0,0);

    public LRUCache(int capacity) {
        keyToValue = new HashMap<>(capacity);
        this.capacity = capacity;
        dummy.pre = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.val:-1;
    }

    public void put(int key, int value) {
        if(keyToValue.containsKey(key)){
            Node node = getNode(key);
            node.val = value;
        }else {
            Node node = new Node(key, value);
            keyToValue.put(key,node);
            putFront(node);
            if(keyToValue.size() > capacity){
                Node lastNode = dummy.pre;
                remove(lastNode);
                keyToValue.remove(lastNode.key);
            }
        }
    }

    public Node getNode(int key){
        if(keyToValue.containsKey(key)){
            Node value = keyToValue.get(key);
            remove(value);
            putFront(value);
            return value;
        }
        return null;
    }
    public void remove(Node value){
        Node pre = value.pre;
        Node next = value.next;
        pre.next = next;
        next.pre = pre;
    }
    public void putFront(Node value){
        Node tmp = dummy.next;
        dummy.next = value;
        value.pre = dummy;
        value.next = tmp;
        tmp.pre = value;
    }
}