LeetCode中关于链表相关算法的整理

关于单链表、双向链表以及在LeetCode中出现的题目的相关解法的总结。注：所有代码来自互联网。

单链表反转

链表反转前

1->2->3->4->5

链表反转后

1<-2<-3<-4<-5

头结点插入法

即在链表的头部依次插入新的节点来完成反转，需要一个新的头结点来将这一过程进行「串联」，在每次将当前节点插入到新的头结点前注意保护当前节点在原链表中的next的节点数据，防止断链。

为了解决断链的情况，我们就需要在节点指针改变指向之前，把当前节点的下一个节点先记下来，等到当前节点的指针完成转向后，遍历指针直接移动到刚刚被记住的那个节点，这样就能防止断链的情况了。

/**
 * 头插法建立新链表，使用两个指针
 */
public static ListNode reverseListByInsertion(ListNode head){
    if(head == null) return null;

    ListNode previous = null;   //记录上个节点
    ListNode newHead = null;    //头插法的新头节点

    while(head != null){
        newHead = new ListNode(head.val);   //新建头结点
        newHead.next = previous; // next指向链表头部

        previous = newHead; // 移动到新的头结点位置
        head = head.next;   //下一个节点
    }
    return newHead;
}

最终新的链表的newHead和原来链表是两个独立的链表，老链表的结构没有改变，仍然是正序的链表。函数内只是改变head临时变量的指向，外层传入的链表实例并没有遭到破坏。

注意，由于代码里的next指针的指向都是新的节点，老的节点本身并没有改变，所以原链表没有结构上的改变。

就地反转法

头结点插入法 的实质是重新创建了一个新的链表，通过遍历待反转链表，将链表每一个节点插入到创建的链表中，然后得到的这个创建的链表就是反转后的链表。而 就地反转 实质就是在待反转链表基础上修改节点顺序得到反转链表。

使用三个指针指向：当前节点A，下个节点B，以及下下个节点C。

遍历时，如下首先记录下下个节点C，然后节点B的指针断开并指向A。然后移动进入下一组。

A -> B -> C -> D -> E

A <- B C -> D -> E

Java版本

/**
 * 使用三个指针原地反转单链表
 */
public static ListNode reverseListLocally(ListNode head){
    if(head == null) return null;

    ListNode a = head;      //当前节点A
    ListNode b = head.next; //下个节点B
    ListNode temp;          //下下个节点C

    //头结点的指针先清空，原链表结构被改变
    head.next = null;

    //有可能链表只有一个节点，所以需要看b是否为null
    while(b != null){
        temp = b.next;  // 记录C节点
        b.next = a;     // a->b 反向，改变的是原链表节点的指向，结构被破坏

        if(temp == null){
            break;
        }
        a = b;      //移动到下一个节点
        b = temp;
    }
    return b == null ? a : b;
}

代码中需要注意的一点是，需要将原链表的头结点的next指针清空，否则就会产生前两个节点的循环指针。不好理解的话，可以这样认为：第一次产生原节点的指针改变是第一次循环时的 b.next=a ，而此时b是头结点的下一个节点，此后循环处理都是从该节点开始的，所以第一个节点的next指向的没有机会被改变，所以要单独处理。

C语言版本

还有一种 C 语言的写法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
               
        if (head == NULL || head->next == NULL)     /* 空链或只有一个结点，直接返回头指针 */
        {
            return head;            
        }
        else                                        /* 至少有两个结点 */
        {
            ListNode * p1 = head;                   /* 第一个结点 */
            ListNode * p2 = p1->next;               /* 第二个结点 */
            ListNode * p3 = p2->next;               /* 第三个结点 */

            while (p2)                              /* 第二个结点为空，到链尾，结束 */
            {
                p3 = p2->next;                      /* 保存第二个节点后面的节点，即p3 */
                p2->next = p1;                      /* 第二个结点指向第一个结点，进行next反转 */
                p1 = p2;                            /* 第一个结点往后移，为下一个待插入节点的next反转准备 */
                p2 = p3;                            /* 第二个结点往后移，将原链表的后续部分还原给p2以便继续遍历 */
            }
            
            head->next = NULL;          /* 第一个结点也就是反转后的最后一个节点指向 NULL */
            head = p1;                  /* 头结点指向反转后的第一个节点 */
            return head;
        }
    }
};

默认传递进来的是 head 节点，并且该节点是携带有效数据的。定义了三个临时节点：

p1 从 head 开始，是老链表的第一个节点，也是新链表构建时的下一个节点，每轮都会移动到刚接入的节点的位置，即后移 p1 = p2 ，可以看做是织毛衣时打的最后一个扣，便于下一针串进来，因为每次织入新的一针都会形成一个新的扣，即 p1 会每次都移动到后一位的位置，即后移 p1 = p2
p2 即为 p1 后的节点，初始为 p1->next ，为遍历原链表的变量节点，也用于逆转链表，所以每次都指向本轮的 p1 ，即 p2->next = p1 ，即 p2 作为新的一针，需要插入到前面的扣中，即p2->next = p1
p3 即为 p2 后的节点，初始为 p2->next ，也就是上面算法中的 tempList ，仅用于保存本轮待反转节点的后面的节点

相比较来说，第二个版本更容易理解一下。算法1中的 resultList.next 就相当于算法2中的 p1 ，而算法1中的 p1 就相当于算法2中的 p3 。

即算法1中用 p1.next 记录了 pNext 的下一个节点，而 pNext 节点的反转指向协助工作依赖的是 resultList.next 变量。

在算法2中这两个功能分别由 p3 和 p1 承担。

递归实现

还有一种递归的实现方法：

基线条件：空链或只有一个结点，直接返回头指针
递归条件：递归调用，返回子链表反转后的头指针

Solution {
public:
    ListNode* reverseList(ListNode* head) {
    
        if (head == NULL || head->next == NULL)     /* 空链或只有一个结点，直接返回头指针 */
        {
            return head;            
        }

        else                                        /* 有两个以上结点 */
        {
            ListNode *new_head = reverseList(head->next); /* 反转以第二个结点为头的子链表 */
            
            /* head->next 此时指向子链表的最后一个结点
            
            /* 将之前的头结点放入子链尾 */
            /* 当前的子链表的尾部节点是当前head节点的next节点，即把head插入到head->next的后面 */
            head->next->next = head;
            /* 清除head的next指针，即当前子链表的最后一个节点的next为null，以便继续递归返回到上层继续插入到该节点的next位置时赋值 */
            /* 如果没有则直接返回当前链表作为结果 */
            head->next = NULL;
            
            /* 注意返回的是new_head即，它的子链表反转后的head，每一次递归返回新的自恋表其头节点均不变（为原链表的最后一个节点），只是长度有变化而已 */
            return new_head;
        }
    }
};

双指针

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

题目的大意是两个链表求和，和也是一个链表（链表是逆序存的数字）这和大数的加减很像，不过这个进位是从后向前。所以可以同时从前往后加，然后保留进位。其实做这种大数加减的题目不管是用的大数组还是链表，都是一样的：

首先做个大循环，对每一位进行操作：

当前位：(A[i]+B[i])%10
进位：（A[i]+B[i]）/10

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0); // 哨兵节点
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next; // d不断向后移动生成新的链表
        }
        if (sum / 10 == 1) // 再延伸一个节点
            d.next = new ListNode(1);
        return sentinel.next; // 返回哨兵节点的next
    }
}

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

链表遍历一遍，同时使用两个指针，一个先启动遍历，移动 n 次后第二个指针再启动。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(-1);  // 防止头被删除
        newhead.next = head; // next指向head
        ListNode point1 = newhead;
        ListNode point2 = newhead;
        for( ; point1 != null; point1 = point1.next, n--)  //point1 控制长度
        {
            if(n < 0)
                point2 = point2.next;   //point2延迟启动
        } 
        point2.next = point2.next.next; // 删除point2的next节点
        return newhead.next;
    }
}

除了用 双指针 外，还可以考虑用递归，凡是这种涉及单链表插入删除操作的时候，都可以考虑用递归，因为 插入和删除都需要涉及被操作节点和它的父节点的操作 。

我们考虑链表的最后一个元素是第 1 层，然后逐级返回，当返回到第 N+1 层（也就是待删除节点的父亲节点所在层数）就开始删除操作。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(-1);
        newhead.next = head;
        remove(newhead, n); 
        return newhead.next;
    }

    // 返回值为当前层序号，最后一层为1，依次向上递增
    private int remove(ListNode node, int n) {
        if(node.next == null) return 1; // 最后一层为1
        int level = remove(node.next, n) + 1; // 递归到下一层，当前层数为子层序号+1
        // 向上回溯的过程依次将参数出栈，就免去了我们使用双指针来标记变量的位置
        if(level == n + 1)    // 递归出口，找到了父亲
            node.next = node.next.next;
        return level;   
    }
}

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list.

思路一：头结点插入法

用新的链表，用头结点的next指针依次指向当前两个链表的最小节点，在移动表头位置（注意使用临时节点移动），和单链表反转的第一个思路是一样的。

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode tmp = result;
        while (l1 != null || l2 != null)  {
            if (l2 == null || (l1 != null && l1.val <= l2.val)) {
                tmp.next = l1; // 插入到头结点
                l1 = l1.next; // 移动
            }
            else {
                tmp.next = l2; // 插入到头结点
                l2 = l2.next; // 移动
            }
            tmp = tmp.next; // 移动
        }
        return result.next;
    }
}

思路2：递归方案

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    ListNode head = null;
    if (l1.val <= l2.val) {
        // 注意不要直接引用原链表，否则会破坏结构
        // 如果不想浪费空间则直接引用l1即可，但破坏了原链表的结构
        head = new ListNode(l1.val); 
        head.next = mergeTwoLists(l1.next, l2);
    } else {
        head = new ListNode(l2.val);
        head.next = mergeTwoLists(l1, l2.next);
    }
    return head;
}

为什么可以用递归，因为参数是有序的且是可以迭代的，并且结果是需要依赖有序这一特性的。

可以结合二叉树的父节点和子节点来考虑，递归时，需要递归到子节点完成计算并返回数据给上一层，进而完成数据的层层整合。这里的整合就是通过上一层节点的next指向下一级返回的结果，这里的结果是一个链表（即使是null）。

还有一点需要注意，不要破坏形参的链表结构，在改变next时尤其需要注意，本方案的空间复杂度为O(M+N) ，即两个链表的长度。如果要求节省空间，那只能破坏两个链表的结构，达到无空间复杂度（不算递归的堆栈数据的保存），但后果就是 l1和l2的结构都变了，第一个节点较小的那个链表和最终结果一样，都是一个合并好的完整有序链表，而另外一个则变成自身原有链表的头结点为开始节点的，整合了两个链表小于该节点的有序链表。

参数的顺序排列对结果没有影响，内部会用相同的规则选择更小的子节点的值为头结点返回。

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

如果涉及到链表交换操作，那么它至少涉及3个节点：当前节点，当前节点的父亲，当前节点的孩子，这里由于我们循环是从前往后走的，所以我们这里使用：当前节点，当前节点的孩子，当前节点的孙子，可能更方便些。

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null)
            return null;
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode current = newhead; // 注意开始位置
        // 保证current后至少有两个节点
        while (current.next != null && current.next.next != null) { 
            ListNode first = current.next;
            ListNode second = current.next.next;
            // 先改变first的指针到second的后面的元素
            first.next = second.next;
            // 再改变current的指向为second
            current.next = second; 
            // 再改变second的指向为first
            current.next.next = first; 
            // 移动current节点，跳过两个节点
            current = current.next.next; 
        }
        return newhead.next;
    }
}

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

这题明显就是 Merge two sorted list 的升级版，我们知道，那题我们可以用 2 个指针完成，但是这题，难道要用 K 个指针？

这里采用 二路归并 的思路，每次只合并两个链表，并将排序后的链表放到较小的下标的位置，然后对所有合并过的链表再继续进行两两合并，直到不能再合并位置。最多合并 logn 次。

假设 K=4：

第一轮 gap 为 1

先合并L[0]，L[1]，结果放到L[0]
然后合并L[2]，L[3]，结果放到L[2]

第二轮 gap 为 1*2

合并L[0]，L[2]，结果放到L[0]

第三轮 gap 为 2*2，溢出

返回L[0]即可

假设 K=5 ，当运行到L[4]的时候它后面没有下个可以和它合并的元素了，所以应该跳出循环，等待 gap 增大时以 下一个 元素的身份参与合并。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0)
        return null;
    
    // double step each loop
    for (int step = 1; step < lists.length; step *= 2) {
        // 遍历所有可以合并的选项，每次都从0位置开始
        // 保证0位置在所有step可能下和后续的位置均会参与了排序合并，最终返回0位置的数据即可
        for (int i = 0; i < lists.length; i += step * 2) {
            // next parter not exists
            if (i + step >= lists.length) {
                break
            };
            
            // merge lists[i] with lists[i+step] and update lists[i]
            lists[i] = mergeTwoLists(lists[i], lists[i + step]);
        }
    }
    
    // lists[0] merge with each sorted list and is the final list    
    return lists[0];
}
    
// 最基本的两个链表的合并
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode tmp = result;
    while (l1 != null || l2 != null) {
        if (l2 == null || (l1 != null && l1.val <= l2.val)) {
            tmp.next = l1;
            l1 = l1.next;
        }
        else {
            tmp.next = l2;
            l2 = l2.next; // 移动位置并不改变原链表的结构
        }
        tmp = tmp.next;
    }
    return result.next;
}

下面通过一个示例进行解释每一轮的过程：

round1

0 1 2 3 4 5 6 7 8 9 10 , step=1

合并位置 i的变化

(0,1) 0+1*2=2

(2,3) 2+1*2=4

(4,5) 4+1*2=6

(6,7) 6+1*2=8

(8,9) 8+1*2=10

(10,[11]) index out of bound!

round2

0’ 2’ 4’ 6’ 8’ 10 , step=1*2=2

（注意除了上面的标记’位置之外，其他位置的数据没有变化）

合并位置 i的变化

(0,2) 0+2*2=4

(4,6) 4+2*2=8

(8,10) 8+2*2=[12] index out of bound!

round3

0’’ 4’’ 8’’ , step=2*2=4

（注意除了上面的标记’‘位置之外，其他位置的数据没有变化）

合并位置 i的变化

(0,4) 0+4*2=8

(8,[12]) index out of bound!

round4

0’’’ 8’’ , step=4*2=8

（注意除了上面的标记’'’位置之外，其他位置的数据没有变化）

合并位置 i的变化

(0,8) 0+8*2=16

([16],[24]) index out of bound!

return 0’’’’

这里很关键的一点是 i += step * 2 ，保证了每一轮的合并都会让两个新的没有合并过的元素进行合并，即 i 和 i + step ，注意每一轮 step 也是增倍的 step *= 2 ，因为每次待合并的两个节点的数据都是在和其之后上一轮 step 取值的位置节点进行合并后的结果，所以 step 下一轮要跳过 2 倍的自己。

其实这个比较的次数一点都不比从第一个开始逐步和2.3.4..比较的次数少。

下面的一个实现是基于 分治 思想的，每次将当前链表数组一分为二，保存到新的数组中，然后递归分别合并这两个新的链表数组，最终再将结果进行合并。

class Solution {

    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length - mid];
        for(int i = mid, j=0; i < lists.length; i++, j++){
            l2[j] = lists[i];
        }

        // divide
        ListNode left = mergeKLists(l1);
        ListNode right = mergeKLists(l2);
        // conquer
        return mergeTwoLists(left, right);

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

用一个指针记录下一个需要存储的位置，另外一个指针遍历数组，只有当前元素和前一个元素不相同时才会将新的元素插入到第一个指针标识的位置。

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length < 2) return nums.length;
        int newlen = 1; // 从1开始，因为0位置肯定是独特的
        // 从1开始
        for(int i = 1; i < nums.length; i++)
        {
            if(nums[i] != nums[i - 1]) nums[newlen++] = nums[i];
            // 不相同时才能覆盖newLen标记的位置
        }
    return newlen;
}

Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai).

n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).

Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

用两个指针来限定一个水桶，left和right。 h[i]表示 i 木板高度。 vol_max 表示木桶容量最大值。

由于桶的容量由最短的那个木板决定： vol_max = min(h[left], h[right]) * (right - left)

left 和 right 分别指向两端的木板
left 和 right 都向中央移动，每次移动 left 和 right 中间高度较小的（因为反正都是移动一次，宽度肯定缩小1 ，这时候只能指望高度增加来增加容量，肯定是替换掉高度较小的，才有可能找到更大的容量。）

看新桶子的容量是不是大于 vol_max ，直到 left 和 right 相交

public class Solution {
  public int maxArea(int[] height) {
     int l = 0,r = height.length - 1;
     int i = height[l] > height[r] ? r:l; // 取最矮的值
     int vol, vol_max = height[i] * (r - l);
     while(l < r) // 退出条件，只剩一个木板
     {
         // 如果左边的高度小于右边，即以左边的高度矩形为准，为了找到更大的面积，只能期望左边再高一点，所以要移动left
         if(height[l] < height[r])  l++;
         else r--;
         vol = Math.min(height[l], height[r]) * (r - l);
         if(vol > vol_max)     vol_max = vol;
     }
     return vol_max;
  }
}

还有一种更清晰的写法：

class Solution {
  public int maxArea(int[] height) {
      int i = 0, j = height.length - 1, res = 0;
      while(i < j){
          res = height[i] < height[j] ? 
              Math.max(res, (j - i) * height[i++]): 
              Math.max(res, (j - i) * height[j--]); 
      }
      return res;
  }
}

复杂度分析：

时间复杂度 O(N) ，双指针遍历一次底边宽度 N 。
空间复杂度 O(1) ，指针使用常数额外空间。

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

先将数组排序，再用两个指针从前后扫描逼近真值(注意这个思想，可以让 O(n2) 的复杂度降为 O(n) ，充分利用排序，因为一定会有一个值满足。

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] nums_sorted = new int[nums.length];
        System.arraycopy(nums, 0, nums_sorted, 0, nums.length);
        // QuickSort. O(nlogn)
        Arrays.sort(nums_sorted);

        // Find the two numbers. O(n)
        int start = 0;
        int end = nums_sorted.length;
        // 排序后的数组进行头尾两个指针的遍历，如果不满足一直往中间移动指针
        while(start < end){
            // 默认首尾之和是大于target的，只能把end往中间移动让和小一些
            while(nums_sorted[start] + nums_sorted[--end] > target);
            
            // 如果相等直接退出
            if(nums_sorted[end] + nums_sorted[start] == target)
                break;
            
            // 否则可能是和已经小于target了，只能让start往中间移动，让和再大一些
            while(nums_sorted[++start] + nums_sorted[end] < target);
            
            // 如果相等直接退出，按题目的说明，一定存在
            if(nums_sorted[end] + nums_sorted[start] == target)
                break;
        }

        int[] ret = new int[2];
        int index = 0;
        ret[index++] = start;
        ret[index++] = end;
        return ret;
    }
}

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:

(-1, 0, 1)

(-1, -1, 2)

为了避免三种循环暴力计算，考虑一下如何将 3Sum 问题转变一下：如果我们随机确定了一个数 a，问题是不是就变成了，在剩下的数里面找到 2 个数和为 0-a ，是不是就和 2Sum 问题一样了？

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {       
        Arrays.sort(nums);
        List<List<Integer>> list;
        list = new ArrayList<List<Integer>>();
        int mid, right;
        // left只用循环所有的非正数就行了（不是负数是因为还要考虑[0 0 0]的情况所以是非正数）
        for (int left = 0; left < nums.length && nums[left] <= 0; left++) {
            mid = left + 1; right = nums.length - 1;
            int tmp = 0 - nums[left];
            // 跳过left重复匹配
            if(left > 0 && nums[left] == nums[left-1])
                continue;
            while(mid < right) {
                if(nums[mid] + nums[right] == tmp) {
                    int tmp_mid = nums[mid], tmp_right = nums[right];
                    list.add(Arrays.asList(nums[left], nums[mid], nums[right]));
                    // 跳过right和mid的重复匹配
                    while(mid < right && nums[++mid] == tmp_mid);
                    while(mid < right && nums[--right] == tmp_right);
                }
                else if(nums[mid] + nums[right] < tmp)
                    mid++; // mid向后移动好使得和变大
                else
                    right--; // right向前移动好使得和变小
            }
        }
        return list;
    }
}

双向链表

实现LRU

基于双向链表可以实现对元素的快速移动和首尾元素的快速定位，可以用来实现LRU算法。

将最近访问的元素移动到链表的头部，将超过大小的数据从尾部移除，将更新过的数据从原链表中删除后再插入到链表头部。

public class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache; // 使用Map来实现缓存
    private final Node head;
    private final Node tail;
    
    /**
     * Remember capacity.
     * Create cache map and doubly linked list.
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
    /**
     * Check key in cache.
     * If not in cache, return -1.
     * If in cache, get the node, move it to head, return its value.
     */
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        moveToHead(node); // 每次访问都要将被访问元素移动到链表头部
        return node.val;
    }
    
    /**
     * If key already in cache, only need to update value:
     * | Get the node, update its value, move to head.
     * If key is not in cache:
     * | Create a new node.
     * | Add it to the head of list and put it in cache.
     * | If cache size exceeds capacity:
     * |   Get the last node, which is the previous node of tail.
     * |   Remove it from list by its self-reference.
     * |   Remove it from cache by its key.
     */
    public void set(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.val = value;
            moveToHead(node); // 每次写都要将对应元素移动到头部
        } else {
            Node newNode = new Node(key, value);
            addNode(newNode); // 添加到链表的头部
            cache.put(key, newNode); // 更新缓存
            
            // 处理缓存容量超限的情况
            if (cache.size() > capacity) {
                Node last = tail.prev;
                removeNode(last); // 删除最后一个元素
                cache.remove(last.key); // 清理缓存
            }
        }
    }
    
    /**
     * Remove node from list and add it to head.
     */
    private void moveToHead(Node node) {
        // 先从原链表中移除该节点
        removeNode(node);
        // 再加入到链表的头部
        addNode(node);
    }
    
    /**
     * Remove a node from double linked list.
     */
    private void removeNode(Node node) {
        // 将node的先后两个节点相连，gc会释放node的内存
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    /**
     * Add a node after head.
     */
    private void addNode(Node node) {
        // 先把node插入到head和它的next之间
        node.prev = head;
        node.next = head.next;
        // 改变head的next的pre
        head.next.prev = node;
        // 改变head的next指向
        head.next = node;
    }
}

References

https://blog.csdn.net/superxiaolong123/article/details/86687733
https://www.cnblogs.com/seniusen/p/9781153.html
https://zhuanlan.zhihu.com/p/66188820

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

LinkedList in LeetCode