18道经典链表题刷题总结——WeetCode1 链表系列

前言：#

WeetCode = Week leetCode 寓意每周刷点leetCode 题目

链表是我恢复刷题手感最喜欢做的系列，其没用太多的算法思想，单纯考验对指针的理解，和coding能力，但是其中也是有一些技巧的，比如哑节点，这个是非常使用的解题技巧，能避免繁琐的if else 处理头部，下面是笔者本周刷的一些链表题目。下周准备刷单调栈，或者树等其他系列题目。

一丶 [ 两数相加](2. 两数相加 - 力扣（Leetcode）)#

思路：#

简简单单就是一手模拟，两个指针分别位于两个链表头，然后一起向右，没经过一个节点，就求和得到sum，如果之前存在进位，那么sum需要加1，然后如果sum大于等于10，需要记录存在进位，方便下一轮判断是否需要进位，然后new除一个链表节点，其值位sum%10。

注意：#

两个链表同时结束，但是最后两个节点值之和存在进位，比如

1->2->3

2->6->8

这时候答案应该是：3->8->1->1，注意最后的1，这里我们需要判断，如果二者同时结束，那么需要在末尾加1
两个链表不是同时结束，这时候有点合并有序数组的意思，需要继续遍历长的链表，并且还是需要处理进位。比如

1->2->3

2->3->8->6->5

答案应该是 3->5->1->（注意到此存在一个进位3+8>10下一个节点应该是1+6）->7->5

代码:#

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //两个链表存在任何一个为null 都返回另外一个
        if(l1 == null ){
            return l2;
        }

        if(l2 == null ){
            return l1;
        }
        
        //记录是否存在进位
        boolean hasCarry = false;
     	//哑巴节点，其next就是头节点
        ListNode preHead = new ListNode();
     	//forward 用来串联求和后生成的节点，其实是结果链表的尾巴
        ListNode forward = preHead;
     	
     	//二者都不为null的时候
         while(l1 != null && l2 != null){
			//求和 如果之前存在进位 那么需要加1
            int sum = (l1.val + l2.val)+ (hasCarry?1:0);
			//记录是否进位 为下轮做准备
            hasCarry = sum>=10;
             //取模
            sum = sum%10;
            //连接
            ListNode newNode = new ListNode(sum);
            forward.next = newNode;
			//一起向下
            forward = forward.next;
            l1 = l1.next;
            l2 = l2.next;
         }
		
       //链表长度相同 且存在进位 那么需要特殊处理
        if(l1 == null && l2 == null ){
            if(hasCarry){
              forward.next = new ListNode(1);
            }
            return preHead.next;
        }
     	//拿到更长的链表
        ListNode longerList = (l1 == null)?l2:l1;
        
     	//继续循环
        while(longerList != null){
            int sum = longerList.val+(hasCarry?1:0);
            hasCarry = sum>=10;
            sum = sum%10;
            ListNode newNode = new ListNode(sum);
            forward.next = newNode;
            forward = forward.next;
            longerList = longerList.next;
        }
	  
       //如果最后还存在进位 那么new 一个节点
       if(hasCarry){
              forward.next = new ListNode(1);
        }
     	
        //返回节点
        return preHead.next;
    }

二丶删除链表的倒数第 N 个结点 #

思路：#

粗暴的思路：先遍历一次拿到链表长度为sz，然后就可以倒数第n是第几个节点了，然后再遍历一次删除即可。但是这样做层次就低了，这时候我们可以使用快慢指针，快指针先走n步，等快指针走到尾部的时候，慢指针就是要删除的倒数第n个节点了。我们可以使用额外的一个指针记录慢指针的前一个，或者使用哑节点，让慢指针从哑节点开始，这样slow最后就是删除节点的前一个

代码:#

  public ListNode removeNthFromEnd(ListNode head, int n) {
         if(head == null || head.next == null){
            return null;
        }
      	//哑节点
        ListNode preHead = new ListNode(-1,head);
        ListNode fast = head;
        ListNode slow = preHead;
		
        //快指针先走
        while(n>0){
            fast=fast.next;
            n--;
        }
        while(fast!=null){
            fast =fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return preHead.next;
    }

三丶[合并两个有序链表](21. 合并两个有序链表 - 力扣（Leetcode）)#

思路：#

没啥好说的，和第一题几乎一模一样

代码：#

 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode preHead = new ListNode();
        ListNode tail = preHead;
        while(list1 != null && list2 != null){
            if(list1.val >= list2.val){
                tail.next = list2;
                ListNode nextNode = list2.next;
                list2.next = null;
                list2 = nextNode;
            }else {
                tail.next = list1;
                ListNode nextNode = list1.next;
                list1.next = null;
                list1 = nextNode;
            }
            tail = tail.next;
        }

        tail.next = list1 == null ? list2 : list1;
        return preHead.next;
    }

四丶合并K个升序链表 #

思路&对应代码：#

1.递归，分治#

第三题我们写了合并两个有序链表，我们把大规模的合并k个分解成n个合并2个即可,首先我们把大任务，分解成合并左半部分，和合并右半部分

和归并排序的思路是一致的

递归的出口是什么，子任务只有一个链表，只是直接返回一个链表即可，子任务只有两个链表，这时候合并两个链表即可
怎么合并两个有序链表，如题三

public ListNode mergeKLists(ListNode[] lists) {
		//入参数组为null 返回null
    //空数组 返回null
        if(lists==null || lists.length==0){
            return null;
        }
    
    	//调用递归方法
        return merge2(lists ,0 ,lists.length-1);
    }
    private ListNode merge2(ListNode[] lists,int start,int end){
		//base case 只有一个链表 直接返回一个链表
        if(start == end){
            return lists[start];
        }
        //子任务只有两个链表
     	 if(start == end-1){
            return mergeTwoLists(lists[start],lists[end]);
        }
        //分治
        int mid = (start+end)/2;
        //合并左边
        ListNode mergeLeft = merge2(lists,start,mid);
		//合并右边
        ListNode mergeRight = merge2(lists,mid+1,end);
        //把左右合并
        return mergeTwoLists(mergeLeft,mergeRight); 
    }
     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode preHead = new ListNode();
        ListNode tail = preHead;
        while(list1 != null && list2 != null){
            if(list1.val >= list2.val){
                tail.next = list2;
                ListNode nextNode = list2.next;
                list2.next = null;
                list2 = nextNode;
            }else {
                tail.next = list1;
                ListNode nextNode = list1.next;
                list1.next = null;
                list1 = nextNode;
            }
            tail = tail.next;
        }

        tail.next = list1 == null ? list2 : list1;
        return preHead.next;
    }

2.优先队列#

我们想下暴力解法，每次合并一个节点就遍历整个数组找最小节点合并，这种做法慢在哪儿，慢在我们需要找到数组中剩下节点中最小节点，进行合并。那么有没有一种数据结构，可以让拿到最小节点的o(1)时间复杂度昵——优先队列

队列优先级是啥——节点的值
队列如何初始化——首先放入数组中所有链表的头节点
队列如何入队——每次一个节点合并的后都把其next节点进行入队
何时停止循环——队列为空、

public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null){
            return null;
        }
        if(lists.length==0){
            return null;
        }
        return mergewithHeap(lists);
    }
	
    private ListNode mergewithHeap(ListNode[] lists){
        //哑节点
        ListNode preHead = new ListNode();
		//尾巴用于串联这些节点
        ListNode tail =preHead;
		//优先队列 传入Comparetor 比较val
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((l1,l2)->l1.val-l2.val);
        //初始化队列
        for(int i = 0;i<lists.length;i++){
            if(lists[i]!=null){
                heap.offer(lists[i]);
            }
           
        }
		
        //队列不为空
        while(!heap.isEmpty()){
            //当前最西澳
           ListNode min =  heap.poll();
			//串联起来
           tail.next =min;
			//更新尾巴
            tail =tail.next;
			//继续入队
            if(min.next!=null){
                heap.offer(min.next);      
           }
          
        }
        return preHead.next;
        
//这里我把优先队列变量名命为heap 是因为java中的优先队列是基于数组的堆实现
//需要注意入队时offer 出队时poll 并且入队不能是null

五丶[两两交换链表中的节点](24. 两两交换链表中的节点 - 力扣（Leetcode）)#

思路：#

简简单单模拟，初始化如下变量

交换s和f 如下效果

接下来需要更新这些变量

如此往复直到f为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; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        

        //没必要交换
        if(head == null || head.next == null){
            return head;
        }

        //只有两个节点
        if(head.next.next == null){
            ListNode newHead = head.next;
            newHead.next = head;
            head.next = null;
            return newHead;
        }

        //哑节点
        ListNode preHead = new ListNode(-1,head);
        ListNode pre = preHead;
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode next = fast.next;
        
        //交换
        while(fast != null){
            

            pre.next = fast;
            fast.next = slow;
            slow.next = next;

            if(next == null){
                return preHead.next;
            }

            pre = slow;
            slow = next;
            fast = slow.next;

            if(fast == null){
                return preHead.next;
            }

            next = fast.next;
        }
    
        return preHead.next;
    }
}

六丶[反转链表](206. 反转链表 - 力扣（Leetcode）)#

思路：#

简简单单模拟

先初始化如下节点

实现反转

更新变量

代码：#

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
	
	    //哑节点
        ListNode preHead = new ListNode(-1,head);
		//当前需要操作的节点
        ListNode cur = head.next;
        //下一个节点
        ListNode next = cur.next;
	   //尾巴
        ListNode tail = preHead.next;

        while(cur != null){
       		//翻转
            cur.next = preHead.next;
            tail.next = next;
            preHead.next = cur;
			
			//更新
            cur = next;
            if(next == null){
                return preHead.next;
            }
            next = next.next; 
        }
        return preHead.next;
    }
}

七丶[K 个一组翻转链表](25. K 个一组翻转链表 - 力扣（Leetcode）)#

思路：#

第六题，我们实现了反转链表，那么k个一翻转的逻辑，这个翻转的过程是一样的，接下来我们只需要把这k个节点先摘下来，然后进行翻转，翻转返回新的头和尾巴，然后和原来链表连接起来继续翻转即可

代码：#

/**
 * 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; }
 * }
 */
class Solution {
    
    public ListNode reverseKGroup(ListNode head, int k) {
		
        //无需翻转的情况
        if(head == null || head.next == null || k == 1){
            return head;
        }
        //哑节点
        ListNode preHead = new ListNode(-1,head);
		
        //翻转后负责把链表重新连接起来
        ListNode pre = preHead;
        
        //翻转 快慢之间的部分
        ListNode slow = head;
        ListNode fast = findKNext(slow,k);
        
        //如果上来就不足k 个 直接g
        if(fast == null){
            return preHead.next;
        }
      
        //循环翻转
       while(fast != null) {
          
         //先保存下 更新的时候需要用
         ListNode next = fast.next;
        
         //断开 不然reverseList会一直翻转下去
         fast.next = null;
         //翻转快慢之间的部分返回翻转后的尾巴
         ListNode[] resArray  = reverseList(slow);
         ListNode rHead = resArray[0];
         ListNode rTail = resArray[1];
		
         // 连接 把翻转后的内容连接上去
         pre.next = rHead;
         rTail.next = next;
         
         //更新
         slow = next;
         fast = findKNext(slow,k);
         pre = rTail;
       }

      return preHead.next;
    }

	//node 慢节点。k是题目中的k个一反转，我们要找到fast
    //如果不足fast 和 slow 之间一共k个节点（包括自己）
    private ListNode findKNext(ListNode node,int k){
        while(k>1){
            if(node == null){
                return null;
            }
            node = node.next;
            k--;
        }
        return node;
    }
    
    //翻转 并返回 头和尾
    private ListNode[] reverseList(ListNode head) {
        
	
	    //哑节点
        ListNode preHead = new ListNode(-1,head);
		//当前需要操作的节点
        ListNode cur = head.next;
        //下一个节点
        ListNode next = cur.next;
	   //尾巴
        ListNode tail = preHead.next;

        while(cur != null){
       		//翻转
            cur.next = preHead.next;
            tail.next = next;
            preHead.next = cur;
			
			//更新
            cur = next;
            if(next == null){
                return  new ListNode[]{preHead.next,tail};
            }
            next = next.next; 
        }
        return new ListNode[]{preHead.next,tail};
    }
}

八丶[旋转链表](61. 旋转链表 - 力扣（Leetcode）)#

思路：#

首先需要注意的是，如果链表长度为len，向右移动len个位置，其实和原本链表一样，所有其实我们只需要移动k%len个位置即可

移动k个，其实就是把最后k个节点连接到链表头部

代码：#

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next==null || k == 0){
            return head;
        }

        //求长度
        ListNode lenTemp = head;
        int len = 0;
        while(lenTemp != null){
            lenTemp = lenTemp.next;
            len ++;
        }

        //我们需要旋转的次数
        k = k % len;
        //刚好整数倍 那么直接返回头
        if(k == 0){
            return head;
        }
        //移动k个，其实就是把最后k个节点连接到链表头部

        //快慢指针找到倒数第k个的前一个
        ListNode fast = head;
        ListNode slow = head;

        while(k!=0){
            fast = fast.next;
            k--;
        } 
        
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }

        //到这fast 就是尾巴 slow是倒数第k+1个 slow.next 就是新的头

        //那么颠倒下倒数k个节点 和 头的位置
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next= head;
        return newHead;
    }
}

九丶[删除排序链表中的重复元素](83. 删除排序链表中的重复元素 - 力扣（Leetcode）)#

思路：#

首先这是一个排序链表，这意味着相同值的节点是相邻的。

初始化一个哑节点p，和新链表的尾巴节点t，c表示当前遍历的节点

如果c和下一个节点值不同那么c可以保留，串到t后，更新到绿色位置，遇到重复的节点，就让c走到最后一个重复的节点，然后让t指向c，后更新t和c继续遍历

代码：#

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         if(head == null || head.next == null){
            return head;
        }
	
        //哑节点
        ListNode preHead = new ListNode(-1,head);
		//尾巴节点
        ListNode tail = preHead;
		//当前遍历的节点
        ListNode cur = head;
        while(cur != null){
            
            //如果下一个节点为空 或者 下一个节点和当前节点值不为空
            //那么当前节点保留，让tail的下一个指向当前节点
            if(cur.next == null || cur.val != cur.next.val){
                tail.next = cur;
                tail = cur;
                cur = cur.next;
                continue;
            }
			
            //到此说明重复了 记录下重复的值
            int duplicateValue = cur.val;
            
            //下一个节点
            ListNode nextNode = cur.next;
            //一直到下一个节点为空 或者值不重复了
            while(nextNode != null && nextNode.val == duplicateValue){
                nextNode = nextNode.next;
            }
			
            //到这就是不重复的 删除这其中的重复的节点
            cur.next = nextNode;

            //连接
            tail.next = cur;
            //刷新进入下一轮循环
            tail = cur;
            cur = cur.next;

        }

        return preHead.next;
    }
}

十丶[删除排序链表中的重复元素 II](82. 删除排序链表中的重复元素 II - 力扣（Leetcode）)#

思路：#

思路和第九题差不多，唯一的差别是重复节点不能保留，所以发生重复的时候需要把tail的下一个节点置为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; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //哑节点
        ListNode preHead = new ListNode(-1,head);
        //新链表尾节点
        ListNode tail = preHead;
        //当前变遍历到的节点
        ListNode cur = head;
        
        
        while(cur != null){
            //如果下一个节点为null 那么必然不会与下一个节点值相同
            //或者下一个节点和当前节点 值不同
            //那么说明当前节点可以假如到新链表中
            //让尾巴的下一个指向当前节点
            if(cur.next == null || cur.val != cur.next.val){
                tail.next = cur;
                tail = cur;
            }

            //如果相同 那么一直到最后一个值相等的节点
            while(cur.next != null && cur.val == cur.next.val){
                //说明这部分重复了，我们首先让新链表不要和这部分连接到一起
                tail.next = null;
                cur = cur.next;
            }
            //cur向下 就必然是不相同的节点
            cur = cur.next;
        }
     

        return preHead.next;
    }
}

十一丶[分隔链表](86. 分隔链表 - 力扣（Leetcode）)#

思路：#

题目乍一看可能没思路，纠结于怎么保持相对顺序不变，其实只需要使用两个哑节点，一个记录大于等于x，一个小于x的节点，最后把这两个哑节点代表的链表的进行串联即可

代码：#

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null){
            return head;
        }

        //小于x的哑节点 和尾节点
        ListNode lessPreHead = new ListNode();
        ListNode lessTail = lessPreHead;

        //大于等于x的哑节点 和尾节点
        ListNode betterEqualHead = new ListNode();
        ListNode betterEqualTail = betterEqualHead;

        ListNode cur = head;

        //遍历
        while(cur != null){
            ListNode curNext = cur.next;

            //如果小于 那么连接到 小于链表上
            if(cur.val < x){
                lessTail.next = cur;
                lessTail = lessTail.next;
                cur.next = null;
            }else{
                //反之连接到大于等于链表
                betterEqualTail.next = cur;
                betterEqualTail = betterEqualTail.next;
                cur.next = null;
            }
            cur = curNext;
        }

        lessPreHead = lessPreHead.next;
        betterEqualHead = betterEqualHead.next;

        //没有大于等于x的节点 那么返回小于头
        if(betterEqualHead == null){
            return lessPreHead;
        }
        //没用小于x的节点 返回大于等于头
         if(lessPreHead == null){
            return betterEqualHead;
        }
        //连接起来
        lessTail.next = betterEqualHead;
        return lessPreHead;
    }

}

十二丶[环形链表](141. 环形链表 - 力扣（Leetcode）)#

思路：#

如果可以使用set缓存所有的节点，然后遍历的时候发现next存在于set中那么可以判断其有环，但是这样空间复杂度为n，所以我们需要记住一个结论，快慢指针都从头开始出发，快指针一次走两步，慢指针一次一步，如果二者相遇说明有环，如果慢指针为null了还没相遇那么说明无环（「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。）

代码：#

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

十三丶[环形链表 II](142. 环形链表 II - 力扣（Leetcode）)#

思路：#

需要记住一个结论，快慢指针同时出发，快一次两步，慢一次一步，相遇的时候就是链表存在环，之后快指针从头开始，慢指针继续运动，二者都一次走一步，相等的时候就是入环节点的位置

代码：#

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


        fast = head;
        while(fast != slow){
            fast =fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

十四丶[复制带随机指针的链表](138. 复制带随机指针的链表 - 力扣（Leetcode）)#

思路：#

如果可以使用map存储每一个节点的下一个节点，和random指针节点，那么这个题就没什么难度，但是如果追求极致的空间不使用额外空间的话，还是有点巧妙的

复制每一个节点的next，并且让复制节点和原节点使用next串联起来，做到如下效果

蓝色是复制的节点，红色是原节点

这时我们其实可以很快的得到蓝色2的random指针指向的是蓝色的4，也就是红色4的next
接下来我们要把两个链表拆开，并且复制random指针

我们遍历到红色2的时候发现，其具备random指向了公司的4，那么蓝色2的指向就是红色4的下一个

代码：#

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null ){
            return null;
        }

        Node cur = head;
        //深拷贝
        while(cur != null){
            Node copy = new Node(cur.val);
            Node next = cur.next;
            cur.next = copy;
            copy.next = next;
            cur = next;
        }

        //拷贝后的头
        Node copyHead = head.next;

        //接下来需要复制random指向
        cur = head;
        while(cur != null){
            Node copy = cur.next;

            //拷贝random
            if(cur.random != null){
                copy.random = cur.random.next;
            }
            cur = copy.next;
        }
        
        //拆分
        cur = head;
        while(cur != null){
            Node copy = cur.next;
            Node sourceNext = copy.next;
            cur.next = sourceNext;
            if(sourceNext != null){
             copy.next = sourceNext.next;
            }
            cur =sourceNext;
        }
        return copyHead;
    }
}

十五丶[LRU 缓存](146. LRU 缓存 - 力扣（Leetcode）)#

思路：#

LRU 最近最少使用，如果看过linkedHashMap源码，我们可以知道，让linkedHashMap按照访问顺序排序然后复写removeEldestEntry让容量大于最大容量的时候删除节点即可实现lru淘汰策略（mybatis源码中的LRU缓存便是如此实现的）。原理便是最近被访问（put 或者get）的内容，放在链表的头部，这样链表的尾部便是最近最少访问的缓存内容，所以我们只要使用链表来维护这个顺序，使用hashMap实现查找即可

代码：#

class LRUCache {

	//双向链表
    static class Node {
        Node pre;
        Node next;
        int key ;
        int val;
    }
	
    //最大容量
    int maxSize;
	//当前容量
    int size=0;
	//头 哑节点
    Node head;
    //尾 哑节点
    Node tail;
	//缓存内容
    Map<Integer,Node> map = new HashMap<>();
    
    //初始化
    public LRUCache(int capacity) {
     maxSize = capacity;
     head = new Node();
     tail = new Node();
     head.next = tail;
     tail.pre = head;
    }

    public int get(int key) {
        
        Node n = map.get(key);
        //缓存中没 返回-1
        if(n == null){
            return -1;
        }

        //缓存中存在，说明最近被使用到 那么调整到队列头部
        adjustToHead(n);

        return n.val;
    }

    public void put(int key, int value) {
       
         Node n = map.get(key);
       	
        //缓存中最开始没用 那么需要 new 一个节点存到map中
        if(n == null){
            n = new Node();
            n.val = value;
            n.key = key;
            map.put(key,n);
            size++;
        }else{
        	//缓存中有 那么改变值
            n.val = value;
        }
        
        //调整到队列头部
        adjustToHead(n);

    }

    //将节点移动到头部 如果容量超过需要删除尾部节点
    void adjustToHead(Node n){
        if(n == head.next){
            //判断是否需要删除最近最少使用的内容
            removeTailIfNeed();
            return;
        }
        
        //调整到头部
        Node sourceFirst = head.next;
        if(n.pre != null){
            n.pre.next = n.next;
            n.next.pre = n.pre;
        }
        n.next = sourceFirst;
        sourceFirst.pre = n;
        n.pre = head;
        head.next = n;
        //判断是否需要删除最近最少使用的内容
        removeTailIfNeed();
    }
	
    //删除最近最少使用的内容
    void removeTailIfNeed(){
        if(size > maxSize){
            map.remove(tail.pre.key);
            size -- ;
            Node needRemove = tail.pre;
            needRemove.pre.next = tail;
            tail.pre = needRemove.pre;
        }

    }
}

十六丶[回文链表](234. 回文链表 - 力扣（Leetcode）)#

思路：#

如果可以使用额外数据结构保存链表中的值，那么这个问题非常简单，但是如果不允许使用额外空间，这个问题就有点巧妙了

首先我们要找到链表的重点（1->2->3找到2，1->2->3->4 找到2）然后将中点右侧部分进行反转，返回再比较中点左半部分和右半部分是否相同的数值，最后还需要把右半部分翻转回来，复原链表

代码：#

/**
 * 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; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        
        //0个节点， 一个节点 直接true
        if(head == null || head.next == null){
            return true;
        }
        //两个节点 看两个节点值是否相同
        if(head.next.next == null){
            return head.val == head.next.val;
        }
        
        //找中点
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //中点
        ListNode half = slow;
        
        //需要翻转的右半部分
        ListNode needReverseHead = half.next;
		//翻转 数组第1个是头 第二个是翻转后的尾
        ListNode[]rArray = reverseList(needReverseHead);
        ListNode halfHead = rArray[0];

        //标记是否 回文
        boolean flag = true;
		//比较是否回文
        while(halfHead!=null){
            flag = halfHead.val==head.val;
            if(!flag){
                break;
            }
            halfHead = halfHead.next;
            head = head.next;
        }
	
        //翻转回去
        ListNode[] recovery = reverseList(rArray[0]);
		//复原链表
        slow.next = recovery[0];

        return flag;


    }

     //翻转 并返回 头和尾
    private ListNode[] reverseList(ListNode head) {
        
        if(head==null){
            return null;
        }
        if(head.next == null){
            return new ListNode[]{head,null};
        }
	    //哑节点
        ListNode preHead = new ListNode(-1,head);
		//当前需要操作的节点
        ListNode cur = head.next;
        //下一个节点
        ListNode next = cur.next;
	   //尾巴
        ListNode tail = preHead.next;

        while(cur != null){
       		//翻转
            cur.next = preHead.next;
            tail.next = next;
            preHead.next = cur;
			
			//更新
            cur = next;
            if(next == null){
                return  new ListNode[]{preHead.next,tail};
            }
            next = next.next; 
        }
        return new ListNode[]{preHead.next,tail};
    }
}

相关阅读:
亚马逊应该如何去做？才能月入万+
期末复习 C语言再学习
 群公告详情
 .Net使用ElasticSearch
【前后缀统计】面试题 05.03. 翻转数位
 不重新安装Anaconda找回不见的Anaconda Prompt
EasyRecovery数据恢复软件恢复了我两年前的照片视频数据
 怎么给PDF添加页面？推荐三个PDF如何插入页面小妙招
 开环零点与闭环零点对系统的影响
 常用网络编程函数
原文地址：https://www.cnblogs.com/cuzzz/p/16907466.html

18道经典链表题刷题总结——WeetCode1 链表系列

前言：#

一丶 [ 两数相加](2. 两数相加 - 力扣（Leetcode）)#

思路：#

注意：#

代码:#

二丶 删除链表的倒数第 N 个结点 #

思路：#

代码:#

三丶[合并两个有序链表](21. 合并两个有序链表 - 力扣（Leetcode）)#

思路：#

代码：#

四丶 合并K个升序链表 #

思路&对应代码：#

1.递归，分治#

2.优先队列#

五丶[两两交换链表中的节点](24. 两两交换链表中的节点 - 力扣（Leetcode）)#

思路：#

代码：#

六丶[反转链表](206. 反转链表 - 力扣（Leetcode）)#

思路：#

代码：#

七丶[K 个一组翻转链表](25. K 个一组翻转链表 - 力扣（Leetcode）)#

思路：#

代码：#

八丶[旋转链表](61. 旋转链表 - 力扣（Leetcode）)#

思路：#

代码：#

九丶[删除排序链表中的重复元素](83. 删除排序链表中的重复元素 - 力扣（Leetcode）)#

思路：#

代码：#

十丶[删除排序链表中的重复元素 II](82. 删除排序链表中的重复元素 II - 力扣（Leetcode）)#

思路：#

代码：#

十一丶[分隔链表](86. 分隔链表 - 力扣（Leetcode）)#

思路：#

代码：#

十二丶[环形链表](141. 环形链表 - 力扣（Leetcode）)#

思路：#

代码：#

十三丶[环形链表 II](142. 环形链表 II - 力扣（Leetcode）)#

思路：#

代码：#

十四丶[复制带随机指针的链表](138. 复制带随机指针的链表 - 力扣（Leetcode）)#

思路：#

代码：#

十五丶[LRU 缓存](146. LRU 缓存 - 力扣（Leetcode）)#

思路：#

代码：#

十六丶[回文链表](234. 回文链表 - 力扣（Leetcode）)#

思路：#

代码：#

二丶删除链表的倒数第 N 个结点 #

四丶合并K个升序链表 #