1.重排链表

将给定的单链表 L\ L L： L0→L1→…→Ln−1→LnL0→L_1→…→L{n-1}→L nL0→L1→…→Ln−1→Ln
重新排序为：L0→Ln→L1→Ln−1→L2→Ln−2→…L_0→L_n →L_1→L{n-1}→L2→L{n-2}→…L0→Ln→L1→Ln−1→L2→Ln−2→…
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

  1. public class Solution {
  2.     public void reorderList(ListNode head) {
  3.         if(head == null || head.next == null)
  4.             return;
  6.         // 快满指针找到中间节点
  7.         ListNode fast = head;
  8.         ListNode slow = head;
  9.         while(fast.next != null && fast.next.next != null){
  10.             fast = fast.next.next;
  11.             slow = slow.next;
  12.         }
  13.         // 拆分链表，并反转中间节点之后的链表
  14.         ListNode after = slow.next;
  15.         slow.next = null;
  16.         ListNode pre = null;
  17.         while(after != null){
  18.             ListNode temp = after.next;
  19.             after.next = pre;
  20.             pre = after;
  21.             after = temp;
  22.         }
  23.         // 合并两个链表
  24.         ListNode first = head;
  25.         after = pre;
  26.         while(first != null && after != null){
  27.             ListNode ftemp = first.next;
  28.             ListNode aftemp = after.next;
  29.             first.next = after;
  30.             first = ftemp;
  31.             after.next = first;          
  32.             after = aftemp;         
  33.         }
  34.     }
  35. }

2.翻转链表

利用栈来翻转链表

  1. import java.util.*;
  2. public class Solution {
  3.     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  4.         //用来存储链表中节点的值。
  5.         Stack<Integer> reverse = new Stack<>();
  6.         while(listNode != null){
  7.             reverse.push(listNode.val);
  8.             listNode = listNode.next;
  9.         }
  10.         //创建的题目要求的数据类型来存储反向的节点值。
  11.         ArrayList<Integer> result = new ArrayList<>(); 
  12.         while(!reverse.isEmpty()){
  13.             //将值从栈中弹出，并添加到ArrayList中
  14.             result.add(reverse.pop());
  15.         }
  16.         return result;
  17.     }
  18. }

递归翻转

  1. import java.util.*;
  2. public class Solution {
  3.     ArrayList<Integer> list = new ArrayList();
  4.     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  5.         if(listNode!=null){
  6.             printListFromTailToHead(listNode.next);
  7.             list.add(listNode.val);
  8.         }
  9.         return list;
  10.     }
  11. }

3.LRU

哈希表+双向链表

  1. public class LRUCache {
  2.     private int size; // 当前容量
  3.     private int capacity; // 限制大小
  4.     private Map<Integer, DoubleQueueNode> map; // 数据和链表中节点的映射
  5.     private DoubleQueueNode head; // 头结点 避免null检查
  6.     private DoubleQueueNode tail; // 尾结点 避免null检查
  8.     public LRUCache(int capacity) {
  9.         this.capacity = capacity;
  10.         this.map = new HashMap<>(capacity);
  11.         this.head = new DoubleQueueNode(0, 0);
  12.         this.tail = new DoubleQueueNode(0, 0);
  13.         this.head.next = tail;
  14.     }
  16.     public Integer get(Integer key) {
  18.         DoubleQueueNode node = map.get(key);
  19.         if (node == null) {
  20.             return null;
  21.         }
  23.         // 数据在链表中，则移至链表头部
  24.         moveToHead(node);
  26.         return node.val;
  27.     }
  29.     public Integer put(Integer key, Integer value) {
  31.         Integer oldValue;
  32.         DoubleQueueNode node = map.get(key);
  33.         if (node == null) {
  34.             // 淘汰数据
  35.             eliminate();
  36.             // 数据不在链表中，插入数据至头部
  37.             DoubleQueueNode newNode = new DoubleQueueNode(key, value);
  38.             DoubleQueueNode temp = head.next;
  39.             head.next = newNode;
  40.             newNode.next = temp;
  41.             newNode.pre = head;
  42.             temp.pre = newNode;
  43.             map.put(key, newNode);
  44.             size++;
  45.             oldValue = null;
  46.         } else {
  47.             // 数据在链表中，则移至链表头部
  48.             moveToHead(node);
  49.             oldValue = node.val;
  50.             node.val = value;
  51.         }
  52.         return oldValue;
  53.     }
  55.     public Integer remove(Integer key) {
  56.         DoubleQueueNode deletedNode = map.get(key);
  57.         if (deletedNode == null) {
  58.             return null;
  59.         }
  60.         deletedNode.pre.next = deletedNode.next;
  61.         deletedNode.next.pre = deletedNode.pre;
  62.         map.remove(key);
  63.         return deletedNode.val;
  64.     }
  66.     // 将节点插入至头部节点
  67.     private void moveToHead(DoubleQueueNode node) {
  68.         node.pre.next = node.next;
  69.         node.next.pre = node.pre;
  70.         DoubleQueueNode temp = head.next;
  71.         head.next = node;
  72.         node.next = temp;
  73.         node.pre = head;
  74.         temp.pre = node;
  75.     }
  77.     private void eliminate() {
  78.         if (size < capacity) {
  79.             return;
  80.         }
  82.         // 将链表中最后一个节点去除
  83.         DoubleQueueNode last = tail.pre;
  84.         map.remove(last.key);
  85.         last.pre.next = tail;
  86.         tail.pre = last.pre;
  87.         size--;
  88.         last = null;
  89.     }
  90. }
  92. // 双向链表节点
  93. class DoubleQueueNode {
  94.     int key;
  95.     int val;
  96.     DoubleQueueNode pre;
  97.     DoubleQueueNode next;
  98.     public DoubleQueueNode(int key, int val) {
  99.         this.key = key;
  100.         this.val = val;
  101.     }
  102. }