ListNode相关

2. 链表相关题目

2.1 合并两个有序链表（简单）：递归

2.2 删除排序链表中的重复元素（简单）：一次遍历

2.3 两链表相加（中等）：递归

2.4 删除链表倒数第N个节点（中等）：倒数第N个元素是遍历的第L-N+1个元素

2.5 两两交换链表中的节点（中等）：递归

2.6 旋转链表（中等）：链表成环后断开

2.7 判断是否存在环形链表（简单）：Set集合 + 重复判断

2.8 环形链表若存在返回其入环的第一个节点（中等）：Set集合 + 重复判断

2.9 LRU缓存(中等，也可以说困难)：哈希表 + 双向链表

2.10 反转链表（简单）：迭代

2.11 分隔链表（中等）：

2.12 反转给定节点处的链表（中等）：穿针引线

2.13 链表的总结

2. 链表相关题目

2.1 合并两个有序链表（简单）：递归

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

思想：将两个链表头部值中较小的一个节点和剩下元素的merge操作合并

总结：将链表头部单独拿出来先比较，比较完后确立了合并链表的头部，剩下的元素按照这种思路继续比较

代码：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //判断 list1 或者 list2 是否为空，为空则直接返回
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }//如果list1头部更小，则list1头部作为合并后链表的头部，然后继续合并其它链表
        else if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }//如果list2头部更小，则list2头部作为合并后链表的头部，然后继续合并其它链表
        else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

2.2 删除排序链表中的重复元素（简单）：一次遍历

题目：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表

思想：给定的链表是已经排好序的，重复的元素在链表中出现的位置是连续的；因此我们比较curr和curr.next，若相等则删除curr.next

总结：curr.next不为空时判断：curr和curr.next是否相等

相等则删除curr.next；
不相等则继续判断下一个节点

代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return head;
    }
}

2.3 两链表相加（中等）：递归

题目：给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思想：链表都是逆序存储数字的，因此链表中同一位置的数可以直接相加；且

sum = l1.val + l2.val + carry
存入结果链表的是 % 10之后的值
下一次的carry是 / 10之后的值

总结：使用递归法，将每一次的sum求出，然后十进制转换后存入结果链表

代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    public ListNode add(ListNode l1, ListNode l2, int carry){
        //如果l1、l2为空，且此时carry进位为0;则返回null
        if(l1 == null && l2 == null && carry == 0){
            return null;
        }
        //sum = l1.val + l2.val + carry
        if(l1 != null){
            carry += l1.val;
            l1 = l1.next;
        }
        if(l2 != null){
            carry += l2.val;
            l2 = l2.next;
        }
        //将相加后的数 % 10，然后存入结果链表
        ListNode result = new ListNode(carry % 10);

        //递归：并将新的carry值传入，为下一次sum做准备
        result.next = add(l1, l2, carry / 10);

        return result;
    }
}

2.4 删除链表倒数第N个节点（中等）：倒数第N个元素是遍历的第L-N+1个元素

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

思想：首先得到链表的长度L，从头节点开始遍历到第L - N + 1个节点时，该节点就是需要删除的节点；

总结：创建一个哑节点，用来指向链表的第一个节点；从头节点开始遍历1 --> L - N - 1，该节点的下一个节点即是待删除元素

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //创建一个哑节点，指向第一个元素
        ListNode dummy = new ListNode(0,head);

        //获取链表长度
        int length = getLength(head);

        //将哑节点作为当前元素
        ListNode curr = dummy;

        //获得倒数第N个节点的前一个结点：从i = 1 遍历到l - n + 1之前，第l - n + 1个节点就是该节点
        for(int i = 1; i < length - n + 1; i++){
            //每遍历一次，都将下一个节点值赋给该节点
            curr = curr.next;
        }

        //遍历完后，下一个节点值就是待删除节点值
        curr.next = curr.next.next;

        ListNode result = dummy.next;
        return  result;

    }

    public int getLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}

2.5 两两交换链表中的节点（中等）：递归

题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题

思想：首先交换头节点和第二个节点的位置，然后递归的实现第三个节点、第四个节点、、、的交换；结束条件是链表中没有节点或者只剩下一个节点

原始链表的头节点head：新链表的第二个节点

原始链表的第二个节点：新链表的头节点newhead
原始链表其他节点的头节点：newhead
原始链表其他节点交换后是放在原始链表头部节点（此时是新链表的第二个节点）的后面的

总结：重点是交换时的顺序：

先找到新链表的头节点
然后根据新链表的头节点找到该节点在原始链表中的下一个节点来递归
最后将原始节点的头节点作为新链表的第二个节点

代码：

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        //原始链表头部的下一个节点就是新链表的头节点
        ListNode newHead = head.next;
        
        //这两行的顺序不能变化，因为此时是对原始链表的第三个节点进行的交换，若先将head赋值给newHead.next就没有了意义
        
        //新链表头节点在原始链表中的下一个节点（第三个节点）就是head的下一个节点
        head.next = swapPairs(newHead.next);

        //head是新链表节点的下一个节点
        newHead.next = head;

        return newHead;
    }
}

2.6 旋转链表（中等）：链表成环后断开

题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

思想：若链表长度为n则：

若向右移动的k >= n时，实际上移动k mod n次
新链表的最后一个节点是原链表的第 (n-1)-(k mod n)个节点
将链表连接成环：将链表的尾节点连接上头节点，然后找到新链表的最后一个节点，将其断开即可

总结：创建一个哑节点，用来指向链表的第一个节点；从头节点开始遍历1 --> L - N - 1，该节点的下一个节点即是待删除元素

代码：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        //1.若不移动或者根节点为空或者只有一个根节点
        if(k == 0 || head == null || head.next == null){
            return head;
        }

        //2.计算出链表长度（从1开始计数，此时即head一定有值）
        int n = 1;
        ListNode curr = head;
        while(curr.next != null){
            n++;
            curr = curr.next;
        }

        //3.新链表的最后一个节点是原链表的第n - k mod n个节点（从1开始计数）
        int add = n - k % n;
        //如果最后一个节点n - k mod n等于原链表的第n个节点，说明k为n的倍数，不需要旋转
        if(add == n){
            return head;
        }

        //4.将链表成环，然后找到新链表的最后一个节点（原链表的第n -（k mod n）个节点），将其断开
        curr.next = head; //链表成环

        //找到旋转后新链表的最后一个节点
        while(add > 0){
            curr = curr.next;
            add--;
        }
        //闭环中，新链表的最后一个节点的下一个节点就是新链表的头节点
        ListNode result = curr.next;

        //将环断开
        curr.next = null;

        return result;

    }
}

2.7 判断是否存在环形链表（简单）：Set集合 + 重复判断

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

思想：遍历所有节点，每遍历到一个节点，就存入哈希表中，并判断该节点是否被访问过（如果存在环形链表，则遍历的过程中会出现环形链表的节点会被访问两次，第一个被访问两次的节点就是环形链表的头节点位置），若访问过则说明是环形链表

总结：遍历链表，存入set集合，利用set集合的自身特性来判断

代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
        //用一个HashSet集合存储每次遍历过程中链表中的节点
        Set<ListNode> set = new HashSet<>();

        while(head != null){
            //set是无需不可重复的，若set.add()返回false，说明已添加过该节点
            if(!set.add(head)){
                return true;
            }
            //节点后移
            head = head.next;
        }

        //遍历结束仍不存在相同节点，说明没有环形链表存在
        return false;
    }
}

2.8 环形链表若存在返回其入环的第一个节点（中等）：Set集合 + 重复判断

题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

思想：遍历所有节点，每遍历到一个节点，就存入哈希表中，并判断该节点是否被访问过（如果存在环形链表，则遍历的过程中会出现环形链表的节点会被访问两次，第一个被访问两次的节点就是环形链表的头节点位置），若访问过则说明是环形链表，且第一个访问到的重复访问节点就是入环的第一个节点

总结：遍历链表，存入set集合，利用set集合的自身特性来判断：如果存在则直接返回该节点，不存在则加入set中

代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //创建存储集合set
        Set<ListNode> set = new HashSet<>();
        ListNode curr = head;

        //遍历链表中的所有值
        while(curr != null){
            //判断是否存在重复节点：存在一定是第一个节点，直接返回，不存在则继续遍历下一个
            if(set.contains(curr)){
                return curr;
            }else{
                set.add(curr);
            }
            curr = curr.next;
        }
        //不存在返回null
        return null;
    }
}

2.9 LRU缓存(中等，也可以说困难)：哈希表 + 双向链表

题目：请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思想：

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1)O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

对于get 操作，首先判断 key 是否存在：
- 如果 key不存在，则返回 −1；
- 如果key 存在，则key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

对于put操作，首先判断 key是否存在：
- 如果 key 不存在，使用key和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果key 存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

总结：遍历链表，存入set集合，利用set集合的自身特性来判断：如果存在则直接返回该节点，不存在则加入set中

代码：

class LRUCache {
    class MyLinkedNode{
        int key;
        int value;
        MyLinkedNode prev;
        MyLinkedNode next;
        public MyLinkedNode(){
        }
        public MyLinkedNode(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    //需要使用哈希表和双向链表需要自己实现来实现
    //哈希表用来快速定位缓存中的元素所在位置，从而方便的get与put;哈希表中存储索引值和双向链表值，链表有key及value
    private Map<Integer,MyLinkedNode> cache = new HashMap<>();

    //记录链表长度
    private int size;
    //记录LRU容量
    private int capacity;
    //定义两个哑节点用来指向链表的头尾节点
    private MyLinkedNode head;
    private MyLinkedNode tail;

    //创建时：定义LRU的size与capacity；并创建头尾伪节点
    public LRUCache(int capacity) {
        this.size = size;
        this.capacity = capacity;
        //构建头尾指针
        head = new MyLinkedNode();
        tail = new MyLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    //get时：先判断Map是否存在该节点，若不存在返回-1；若存在则将其展示，并把它移动到双向链表的头部
    public int get(int key) {
        MyLinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        //将节点移动到双向链表的头部
        moveToHead(node);
        return node.value;
    }
    
    //put时：先判断Map中是否存在该节点，若存在则直接改变value，并将其移动到头部；
    //若不存在，则将其添加到哈希表和链表头部，并判断当链表长度size>LRU容量则将链表尾部节点删除
    public void put(int key, int value) {
        MyLinkedNode node = cache.get(key);
        if(node != null){
            //存在该节点则改变其value值
            node.value = value;
            moveToHead(node);
        }else{
            //将节点添加到链表和哈希表中，然后移动到链表头部
            MyLinkedNode newNode = new MyLinkedNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;

            //判断是否超出容量：超出则在链表和哈希表中删除尾部节点
            if(size > capacity){
                MyLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        }
    }

    public void moveToHead(MyLinkedNode node){
        removeNode(node);
        addToHead(node);
    }

    //删除节点
    public void removeNode(MyLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //将节点添加到头部
    public void addToHead(MyLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    //删除尾部节点:拿到尾部节点，然后删除并返回删除后的节点
    public MyLinkedNode removeTail(){
        MyLinkedNode result = tail.prev;
        removeNode(result);
        return result;
    }
}

2.10 反转链表（简单）：迭代

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思想：遍历链表，让遍历的节点的next指向前一个节点；注意：头节点没有引用前一个节点，因此要先存储一个前节点为null；并且要创建一个新节点，最终返回新的链表头部

总结：在进行反转时，需要变化的量有：节点值（为了迭代变为下一个节点值）、节点的下一个值（指向节点的上一个值）、节点的上一个值（为了迭代每次变为上一次迭代的当前节点值）

代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        //创建一个空节点，用来指向null
        ListNode prev = null;
        //创建一个临时节点
        ListNode curr = head;

        //如果当前节点不为空：反转链表时：
        //当前节点的下一个节点先存下来，然后将让当前节点的next指向前一个结点；
        //每轮循环中，前一个节点都是上一次循环的当前节点
        while(curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

2.11 分隔链表（中等）：

题目：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。保留两个分区中每个节点的初始相对位置

思想：维护两个链表samll和large，按照顺序分别存储小于x的节点值和大于等于x的节点值，最后将前一个链表的尾节点指向钱一个链表的头节点即可

总结：为防止头节点的边界条件（需要对头节点进行特殊判断，为了防止这个特殊判断），设置一个哑节点指向头节点

代码：

class Solution {
    public ListNode partition(ListNode head, int x) {
        //创建两个链表，分别用来存储小于x和大于等于x的节点
        ListNode small = new ListNode(0);
        ListNode large = new ListNode(0);

        //创建两个哑节点，此时哑节点并不指向新链表的头节点，而是等于头节点（后面讲头节点改为新添加的节点）
        ListNode smallHead = small;
        ListNode largeHead = large;

        //遍历当前链表值，根据与x的比较存入两个新链表
        while(head != null){
            //将小于x的节点存入small链表，并更改头部
            if(head.val < x){
                small.next = head;
                small = small.next;
            }//将大于等于x的节点存入large链表，并更改头部
            else{
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        //将samll的尾节点指向large的头节点
        small.next = largeHead.next;
        //将large的尾节点指向nul
        large.next = null;
        return smallHead.next;
    }
}

2.12 反转给定节点处的链表（中等）：穿针引线

思想：先将需要反转的位置进行反转得到反转后链表，然后将left的前一个节点prev指向反转后的链表的头部，将反转后链表的尾部指向right的next节点即可

总结：只要是头节点可能发生变化的情况，都设置一个哑节点，用来处理这种特殊情况；

代码：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //创建一个哑节点，指向链表头部
        ListNode dummy = new ListNode();
        dummy.next = head;

        //一开始记left的前一个节点为哑节点，然后从哑节点出发走left - 1步，找到left节点的前一个节点prev
        ListNode prev = dummy;
        for(int i = 0; i < left - 1; i++){
            prev = prev.next;
        }

        //从prev出发，走right - left + 1 步，找到right节点
        ListNode rightNode = prev;
        for(int i = 0; i < right - left + 1; i++){
            rightNode = rightNode.next;
        }

        //先将prev的下一个节点left和rightNode的下一个节点next保存起来，然后将链表截断
        ListNode leftNode = prev.next;
        ListNode next = rightNode.next;
        prev.next = null;
        rightNode.next = null;

        //将截断后的元素进行反转
        reverseListNode(leftNode);

        //让prev节点指向新链表的头节点（rightNode），新链表的尾节点（leftNode）指向保存下的next节点
        prev.next = rightNode;
        leftNode.next = next;
        return dummy.next;

    }

    public void reverseListNode(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
    }
}