线性表
定义：线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
数组
定义：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
特性
**数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)*
a[i]_address = base_address + i * data_type_size
插入
- 如果数组有序，如果要将某个数据插入到第 k 个位置，则插入操作需要多次的数据搬移工作来清空该位置，为插入操作进行准备，这时候的平均时间复杂度O(n) = (1+2+3+...+n)/n = O(n)
- 如果数组无序，如果要将某个数据插入到第 k 个位置，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置，这时候平均时间复杂度就会变成O(1)
删除
与插入类似，如果删除末尾元素，这时候时间复杂度为O(1);如果删除第一个元素，时间复杂度O(n),删除任意位置的平均时间复杂度 = O(n);
-
在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率会提高很多，如JVM的标记清除算法的核心思想
case：数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。
数据批量删除操作为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
查询
- 根据数组下标进行查询，平均时间复杂度 = O(1);
- 根据数组元素进行查询, 因为涉及到数组元素的比较，所以平均时间复杂度 = O(n);
注意事项：
警惕数组下标越界问题
-
ArrayList为防止因扩容操作造成的数据搬移需要注意以下3点：
- 能不使用就不要使用默认构造函数；
- 当知道列表容量的时候，最好用指定的容量来创建实例；
- 不知道列表容量，预估一个稍微大于容量的值来创建实例；
-
容器ArrayList和数据Array比较
- Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
- 当要表示多维数组时，用数组往往会更加直观。比如 Object[][][][] array；而用容器的话则需要这样定义：ArrayList <ArrayList<Object>> arrayList。
小结：
1. 对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
数组相关case
3.盛水最多的容器
链表
单链表
定义：
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“**结点**”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作**后继指针 next**。
其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
插入、删除
与数组插入、删除相比，链表的相关操作不涉及的数据的搬移操作，仅是**改变相邻节点指针的改变**，所以对于的时间复杂度 = **O(1)**;
查询
由于链表地址不连续，无法根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地**依次遍历**，直到找到相应的结点，这时候随机访问的时间复杂度 = **O(n)**。
循环链表
定义
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。
特性：
单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的**数据具有环型结构**特点时，就特别适合采用**循环链表**。比如著名的**约瑟夫问题**。
双向链表
定义
单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
特性
双向链表可以支持 **O(1) 时间复杂度的情况下找到前驱结点**，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：
- 删除结点中“值等于某个给定值”的结点；
- 删除给定指针指向的结点。
对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。
尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！
同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
现在，你有没有觉得双向链表要比单链表更加高效呢？这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。如果你熟悉 Java 语言，你肯定用过 LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理，就会发现其中就用到了双向链表这种数据结构。
实际上，这里有一个更加重要的知识点需要你掌握，那就是用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过用时间换空间的设计思路。
双向循环链表
数组链表比较
链表相关case
链表编写的注意事项：
理解指针或引用的含义
指针或引用：都是存储所指对象的内存地址
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
p->next=q。//这行代码是说，p 结点中的 next 指针存储了 q 结点的内存地址。 p->next=p->next->next。//这行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。
警惕指针丢失和内存泄漏
- 插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。
插入节点
- 删除链表结点时，也一定要记得手动释放内存空间
利用哨兵简化实现难度
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。
//插入操作 new_node->next = p->next; p->next = new_node; //头部插入 if (head == null) { head = new_node; } //删除操作 p->next = p->next->next; //尾结点删除 if (head->next == null) { head = null; } //不带头链表操作 // 在数组a中，查找key，返回key所在的位置 // 其中，n表示数组a的长度 int find(char* a, int n, char key) { // 边界条件处理，如果a为空，或者n<=0，说明数组中没有数据，就不用while循环比较了 if(a == null || n <= 0) { return -1; } int i = 0; // 这里有两个比较操作：i<n和a[i]==key. while (i < n) { if (a[i] == key) { return i; } ++i; } return -1; } //带头链表操作 // 在数组a中，查找key，返回key所在的位置 // 其中，n表示数组a的长度 // 我举2个例子，你可以拿例子走一下代码 // a = {4, 2, 3, 5, 9, 6} n=6 key = 7 // a = {4, 2, 3, 5, 9, 6} n=6 key = 6 int find(char* a, int n, char key) { if(a == null || n <= 0) { return -1; } // 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值 if (a[n-1] == key) { return n-1; } // 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。tmp=6。 // 之所以这样做的目的是：希望find()代码不要改变a数组中的内容 char tmp = a[n-1]; // 把key的值放到a[n-1]中，此时a = {4, 2, 3, 5, 9, 7} a[n-1] = key; int i = 0; // while 循环比起代码一，少了i<n这个比较操作 while (a[i] != key) { ++i; } // 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6} a[n-1] = tmp; if (i == n-1) { // 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1 return -1; } else { // 否则，返回i，就是等于key值的元素的下标 return i; } }带头链表重点留意边界条件处理
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
举例画图，辅助思考 -- 举例法和画图法。
链表--举例法和画图法多写多练，没有捷径
最近最少使用策略 LRU
缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
问题：
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4提示：
1 <= capacity <= 3000 0 <= key <= 3000 0 <= value <= 104 最多调用 3 * 104 次 get 和 put思路：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
优化：思路2：引入散列表（Hash Table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)，同时使用双向链表来获取前一个节点
class LRUCache { private class CacheNode{ private int key; private int value; private CacheNode prev; private CacheNode next; public CacheNode(int key,int value){ this.key = key; this.value =value; this.prev = null; this.next = null; } } private int capacity; // 在时间复杂度O(1)的情况下找到节点 private Map<Integer,CacheNode> cacheNodeMap = new HashMap<Integer,CacheNode>(); //哨兵节点-头节点 private CacheNode head = new CacheNode(-1,-1); //哨兵节点-尾节点 private CacheNode tail = new CacheNode(-1,-1); public LRUCache(int capacity) { this.capacity = capacity; this.head.next = tail; this.tail.prev = head; } public int get(int key) { //不存在，返回-1 if(!cacheNodeMap.containsKey(key)){ return -1; } // 如果存在，则将该节点移动到头部，并返回 CacheNode node = cacheNodeMap.get(key); node.prev.next = node.next; node.next.prev = node.prev; moveToHead(node); return cacheNodeMap.get(key).value; } public void put(int key, int value) { if(this.get(key) != -1){ // 查询到缓存中存在key相同的节点，这时需要将原节点替换为新节点，并更新cacheNodeMap if(this.cacheNodeMap.get(key).value != value){ CacheNode node = this.cacheNodeMap.get(key); node.prev.next = node.next; node.next.prev = node.prev; node = new CacheNode(key,value); moveToHead(node); cacheNodeMap.put(key, node); } }else{ // 未找到，判断缓存是否已满 if(cacheNodeMap.size() >= capacity){ // 如果已满，则删除尾部节点再插入的头部 //删除尾结点 cacheNodeMap.remove(tail.prev.key); CacheNode prevNode = tail.prev.prev; tail.prev = prevNode; prevNode.next = tail; } //插入的头部 CacheNode node = new CacheNode(key,value); moveToHead(node); cacheNodeMap.put(key, node); } } private void moveToHead(CacheNode node){ node.next =head.next; head.next = node; node.prev = head; node.next.prev = node; } }
链表翻转
题目1链接：https://leetcode-cn.com/problems/reverse-linked-list/
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->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 reverseList(ListNode head) { /** * 思路：首先设置三个节点： * prev 前驱节点 --记录翻转后的指向位置 * current 当前节点 * next 后驱节点 -- 用于记录翻转前的指向位置 * 流程：首先判断是否为空链表 head == null，如果为空链表则结束； * 如果不为空，首先prev前驱节点指向 null ，然后current 指向prev节点，整体向后移动一位，循环遍历直到全部遍历完成 * (current == null)结束返回翻转后的头结点prev。 * 边界条件： 0个节点；1个节点；2个节点 * */ if(head == null) return head; ListNode prev = head; ListNode current = prev.next; prev.next = null; while(current != null){ ListNode next = current.next; current.next = prev; prev = current; current = next; } return prev; } }题目2 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->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 { /** *思路：为了保证head节点位置移动的影响，这里设置一个哨兵节点dummy, 这样所有操作完成以后返回dummy.next即可。 *因为需要翻转m ~ n 之间的节点，这里可以从参考上题的解题思路，剩下的就是找到 m 的前驱节点和n的后驱节点的问题并且保持其中的指向 *位置互换即可 *边界条件：head == null 和 m >= n */ public ListNode reverseBetween(ListNode head, int m, int n) { //边界条件的处理 if(head == null || m>=n){ return head; } // 设置哨兵节点 ListNode dummy = new ListNode(-1); dummy.next = head; head = dummy; //找到m的前驱节点 for(int i = 1 ;i < m;i++){ head = head.next; } //必要的节点信息 ListNode prevM = head; ListNode mNode = head.next; ListNode nNode = mNode; ListNode suffN = nNode.next; //翻转m ~ n之间的节点 for(int i = m ;i < n;i++){ ListNode next = suffN.next; suffN.next = nNode; // 节点整体后移1位 nNode = suffN; suffN = next; } //互换m和n的位置 prevM.next = nNode; mNode.next = suffN; return dummy.next; }
深度拷贝带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。示例 1：
复制带随机指针的链表-示例1输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：复制带随机指针的链表-示例2输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：复制带随机指针的链表-示例3输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。提示：
0 <= n <= 1000
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。/** 思路1：1.边界条件处理 2.通过Map 保存1 和 1‘ 的对应关系 3. 复制原链表的指向关系。 /* // 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 { private Map<Node,Node> nodeMap = new HashMap<Node,Node>(); public Node copyRandomList(Node head) { /** *思路1：1. 使用一个集合来存储head和head‘的对应关系。 * 2. 仿照head 配置head’ */ //边界条件处理：判断是非为空 if(head == null){ return head; } Node dummy = new Node(-10001); dummy.next = head; // 循环获取head‘ while(head != null){ Node newHead = new Node(head.val); nodeMap.put(head,newHead); head = head.next; } // 复制next和random的关系 for (Map.Entry<Node,Node> entry : nodeMap.entrySet()) { entry.getValue().next = nodeMap.get(entry.getKey().next); entry.getValue().random = nodeMap.get(entry.getKey().random); } return nodeMap.get(dummy.next); } } //思路2：在原链表中维护1和1‘的指向关系。具体如下： //原链表：1 -> 2 -> 3 //现在链表：1 -> 1' -> 2 ->2' -> 3 -> 3'(目的：维护1和1’的关系) //将复制后的链路拆分出来，并且还原原来的引用关系。 /* // 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) { //思路2：在原链表中维护1和1‘的指向关系。具体如下： //原链表：1 -> 2 -> 3 //现在链表：1 -> 1' -> 2 ->2' -> 3 -> 3'(目的：维护1和1’的关系) //将复制后的链路拆分出来，并且还原原来的引用关系。 //边界条件的处理 if(head == null){ return head; } //新链表：1 -> 1' -> 2 ->2' -> 3 -> 3' copy(head); copyRandom(head); return split(head); } /** * 将新链表的节点,copy到原链表对应节点的next节点上。 */ private void copy(Node head){ Node copyNextNode = head; while(copyNextNode != null){ Node copyNode = new Node(copyNextNode.val); copyNode.next = copyNextNode.next; copyNextNode.next =copyNode; // 移位操作 copyNextNode = copyNode.next; } } /** * 根据原来链表的random 复制新链表的random */ private void copyRandom(Node head){ Node copyRandomNode = head; while(copyRandomNode != null && copyRandomNode.next != null){ if(copyRandomNode.random != null){ copyRandomNode.next.random = copyRandomNode.random.next; }else{ copyRandomNode.next.random = null; } //移位操作 copyRandomNode = copyRandomNode.next.next; } } /** * 拆分成两个链表，并保证两个链表指向的正确性 */ private Node split(Node head){ Node node = head; Node result = node.next; while(node != null && node.next != null){ Node nextNode = node.next.next; Node copyNode = node.next; if(copyNode != null && nextNode != null){ node.next = nextNode; copyNode.next = nextNode.next; }else{ node.next = null; copyNode.next = null; } //移位操作 node = nextNode; } return result; } }
链表相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零/** * 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 addTwoNumbers(ListNode l1, ListNode l2) { //思路1：分别对两个数组遍历求和，然后相加，最后将结果替换成链表。 //优点：简单高效 //缺点：无法满足提示条件，即long类型对结果无法存储 // 思路2：链表相应位置依次相加求和，将进位进行存储，用于下次相加计算,所以操作执行完成返回最终链表-- 即返回最终链表的头即可。 //优点：无序考虑数据求和存储问题。 // 缺点：编码复杂 // 正常条件：l1 != null 且l2 != null; //边界条件包括：l1 == null; l2 == null; l1 == null的时候l2 != null;l2 == null的时候l1 != null; 最近循环完成进位值 != 0 // 优化点：哨兵节点 if(l1 == null){ return l2; } if(l2 == null){ return l1; } //进位值 int carry = 0; // 设置哨兵节点 ListNode sentry = new ListNode(-1); ListNode pre = sentry; while(l1 != null && l2 != null){ int number = l1.val + l2.val + carry; carry = number/10; int sum = number%10; ListNode node = new ListNode(sum); pre.next = node; pre = pre.next; l1 = l1.next; l2 = l2.next; } while(l1 != null){ int number = l1.val + carry; carry = number/10; int sum = number%10; ListNode node = new ListNode(sum); pre.next = node; pre = pre.next; l1 = l1.next; } while(l2 != null){ int number = l2.val + carry; carry = number/10; int sum = number%10; ListNode node = new ListNode(sum); pre.next = node; pre = pre.next; l2 = l2.next; } //循环完成进位值 != 0 if(carry != 0){ ListNode node = new ListNode(carry); pre.next = node; } return sentry.next; } }
[图片上传失败...(image-172d9f-1615721932866)]
/** * 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 addTwoNumbers(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } if(l2 == null){ return l1; } int carry = 0; //哨兵节点 ListNode head = new ListNode(-1); ListNode pre = head; while(l1 != null || l2 != null){ l1 = l1 == null?new ListNode(0):l1; l2 = l2 == null?new ListNode(0):l2; int number = l1.val + l2.val + carry; carry = number/10; int sum = number%10; ListNode node = new ListNode(sum); pre.next = node; pre = pre.next; l1 = l1.next; l2 = l2.next; } if(carry != 0){ ListNode node = new ListNode(carry); pre.next = node; } //返回生成的链表--即返回真正的头结点 return head.next; } }
如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？
跳表
概念
链表加多级索引结构。
优点
- 支持快速插入，删除，查找操作，编写代码要求低，时间复杂度：O(logn).
- 实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
- 为了代码的简单、易读，会用跳表替代红黑树。
