iwehdio的博客园：https://www.cnblogs.com/iwehdio/
学习自：labuladong的算法教程
本文包括链表leetcode相关题目：
- 92、25、234.
- 2、19、21、23、24、25、61、82、83、86.
1、数据结构的基本知识
数据结构的存储方式
- 数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。
- 数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
- 链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
- 「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。
- 「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。
- 「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
- 「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。
数据结构的基本操作
-
对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。
-
数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。
-
如何遍历 + 访问？从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。
-
线性就是 for/while 迭代为代表，非线性就是递归为代表。
-
数组遍历框架，典型的线性迭代结构：
void traverse(int[] arr) { for (int i = 0; i < arr.length; i++) { // 迭代访问 arr[i] } } -
链表遍历框架，兼具迭代和递归结构：
/* 基本的单链表节点 */ class ListNode { int val; ListNode next; } void traverse(ListNode head) { for (ListNode p = head; p != null; p = p.next) { // 迭代访问 p.val } } void traverse(ListNode head) { // 递归访问 head.val traverse(head.next); } -
二叉树遍历框架，典型的非线性递归遍历结构：
/* 基本的二叉树节点 */ class TreeNode { int val; TreeNode left, right; } void traverse(TreeNode root) { // 前序遍历 traverse(root.left) // 中序遍历 traverse(root.right) // 后序遍历 } -
二叉树框架可以扩展为 N 叉树的遍历框架：
/* 基本的 N 叉树节点 */ class TreeNode { int val; TreeNode[] children; } void traverse(TreeNode root) { // 递归访问 root.val for (TreeNode child : root.children) traverse(child); } -
N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。图是可能出现环的，用个布尔数组 visited 做标记就行了。
-
2、链表
- 链表题中的常用命名：
- pred：前驱；
- succ：后继；
- cur：当前；
- nxt：下一个；
- head：头；
- tail：尾。
递归反转链表的一部分
-
单链表节点结构：
// 单链表节点的结构 public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } -
什么叫反转单链表的一部分呢，就是给你一个索引区间，让你把单链表中这部分元素反转，其他部分不变：
- 注意这里的索引是从 1 开始的。
-
迭代的思路大概是：
-
先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。
-
具体的，用两个指针指向要反转的两个节点，用第三个指针指向下一个要反转的节点。prev指向反转完成的链表的头，third指向还未反转的链表的头，cur指向反转的节点。
third = cur.next cur.next = prev prev = cur cur = third -
迭代实现思路看起来虽然简单，但是细节问题很多的，反而不容易写对。相反，递归实现就很简洁优美。
-
-
递归思路：
-
实现代码：
ListNode reverse(ListNode head) { if (head.next == null) return head; ListNode last = reverse(head.next); head.next.next = head; head.next = null; return last; } -
对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的
reverse函数定义是这样的：- **输入一个节点
head，将「以 **head为起点」的链表反转，并返回反转之后的头结点。
- **输入一个节点
-
明白了函数的定义，在来看这个问题。比如说我们想反转这个链表：
-
那么输入
reverse(head)后，会在这里进行递归：ListNode last = reverse(head.next); -
不要跳进递归，而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：
-
这个
reverse(head.next)执行完成后，整个链表就成了这样：
-
并且根据函数定义，
reverse函数会返回反转之后的头结点，我们用变量last接收了。 -
现在再来看下面的代码：
head.next.next = head;
-
接下来：
head.next = null; return last;
-
有两个地方需要注意：
-
递归函数要有 base case，也就是这句：
if (head.next == null) return head;意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。
-
当链表递归反转之后，新的头结点是
last，而之前的head变成了最后一个节点，别忘了链表的末尾要指向 null：head.next = null;
-
-
-
反转链表前n个节点：
-
实现一个这样的函数：
// 将链表的前 n 个节点反转（n <= 链表长度） ListNode reverseN(ListNode head, int n) -
比如说对于下图链表，执行
reverseN(head, 3)：
-
解决思路和反转整个链表差不多，只要稍加修改即可：
ListNode successor = null; // 后驱节点 // 反转以 head 为起点的 n 个节点，返回新的头结点 ListNode reverseN(ListNode head, int n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head.next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode last = reverseN(head.next, n - 1); head.next.next = head; // 让反转之后的 head 节点和后面的节点连起来 head.next = successor; return last; } -
具体的区别：
- base case 变为
n == 1，反转一个元素，就是它本身，同时要记录后驱节点。 - 刚才我们直接把
head.next设置为 null，因为整个链表反转后原来的head变成了整个链表的最后一个节点。但现在head节点在递归反转之后不一定是最后一个节点了，所以要记录后驱successor（第 n + 1 个节点），反转之后将head连接上。
- base case 变为
-
-
反转列表的一部分：
-
现在解决我们最开始提出的问题，给一个索引区间
[m,n]（索引从 1 开始），仅仅反转区间中的链表元素。ListNode reverseBetween(ListNode head, int m, int n) -
首先，如果
m == 1，就相当于反转链表开头的n个元素嘛，也就是我们刚才实现的功能：ListNode reverseBetween(ListNode head, int m, int n) { // base case if (m == 1) { // 相当于反转前 n 个元素 return reverseN(head, n); } // ... } -
如果
m != 1怎么办？如果我们把head的索引视为 1，那么我们是想从第m个元素开始反转对吧；如果把head.next的索引视为 1 呢？那么相对于head.next，反转的区间应该是从第m - 1个元素开始的；那么对于head.next.next呢…… -
区别于迭代思想，这就是递归思想，所以我们可以完成代码：
ListNode reverseBetween(ListNode head, int m, int n) { // base case if (m == 1) { return reverseN(head, n); } // 前进到反转的起点触发 base case head.next = reverseBetween(head.next, m - 1, n - 1); return head; }
-
-
总结：
- 递归的思想处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。这里的定义指的是，递归函数的返回值和递归函数中return的值。
- 处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。
- 值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以考虑效率的话还是使用迭代算法更好。
-
92题 反转列表 Ⅱ：
-
递归思路：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m==1) return reverseStart(head, n); head.next=reverseBetween(head.next, m-1,n-1); return head; } ListNode succ = null; ListNode reverseStart(ListNode head, int n) { if (n==1) { succ=head.next; return head; } ListNode last = reverseStart(head.next, n-1); head.next.next = head; head.next=succ; return last; } } -
迭代思路：
class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if(head==null) return null; ListNode pred = null; ListNode cur = head; //移动到反转位置 while(m-1>0){ pred = cur; cur = cur.next; m--; n--; } //con是前一段链表尾，tail是反转部分的链表尾 ListNode con = pred, tail = cur, temp = null; while(n>0){ temp = cur.next; cur.next = pred; pred = cur; cur = temp; n--; } //结束时，pred是反转部分的链表头，cur是下一段链表头 if(con!=null){ con.next=pred; } else{ head=pred; } tail.next = cur; return head; } }
-
K个一组反转链表
-
子问题：
- 这个问题的子问题其实就是将k个长度的链表反转。
- 还需要考虑的是，反转后，与原链表的连接问题，所以需要维护指向前一段链表的尾和后一段链表的头的指针。
- 最后，递归或迭代的终止条件，就是当不足k个，则不反转。
- 例：k=2，前两个反转后，指向后续链表调用反转函数。
-
递归向后，迭代反转：
class Solution { public ListNode reverseKGroup(ListNode head, int k) { //保存下一段链表的头 ListNode tail = head; for(int i=0; i<k; i++){ if(tail==null) return head; tail = tail.next; } //返回的是反转部分的头 ListNode newHead = reverse(head, k); //head是反转部分的尾 head.next = reverseKGroup(tail,k); return newHead; } ListNode reverse(ListNode head, int num){ //因为在上一层判断过了，所以head必然不为null ListNode cur = head, pred = null, temp = null; while(num-->0){ temp = cur.next; cur.next = pred; pred = cur; cur = temp; } return pred; } }
回文链表
-
这道题的关键在于，单链表无法倒着遍历，无法使用双指针技巧。那么最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。
-
其实，借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表。
-
树结构不过是链表的衍生。那么，链表其实也可以有前序遍历和后序遍历：
void traverse(ListNode head) { // 前序遍历代码 traverse(head.next); // 后序遍历代码 } -
如果想倒序遍历链表，就可以在后序遍历位置操作：
/* 倒序打印单链表中的元素值 */ void traverse(ListNode head) { if (head == null) return; traverse(head.next); // 后序遍历代码 print(head.val); } -
模仿双指针实现回文判断：
class Solution { ListNode left = null; public boolean isPalindrome(ListNode head) { left = head; return traverse(head); } boolean traverse(ListNode right){ if(right==null) return true; boolean res = traverse(right.next); res = res &&(left.val==right.val); left = left.next; return res; } } -
这么做的核心逻辑是什么呢？实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已。
-
当然，无论造一条反转链表还是利用后序遍历，算法的时间和空间复杂度都是 O(N)。下面我们想想，能不能不用额外的空间，解决这个问题。
-
优化思路：
- 通过「双指针技巧」中的快慢指针来找到链表的中点。
- 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步。
- 总之，就是让slow指向后半个需要反转的链表头节点。
- 最后反转链表后，比较值。
class Solution { public boolean isPalindrome(ListNode head) { //设置快慢指针 ListNode fast = head, slow = head; while(fast!=null && fast.next!=null){ fast = fast.next.next; slow = slow.next; } if(fast!=null){ slow = slow.next; } ListNode left = head; ListNode right = reverse(slow); while(right!=null){ if(left.val!=right.val) return false; left = left.next; right = right.next; } return true; } //反转从head开始的节点，返回反转后的头结点 ListNode reverse(ListNode head){ ListNode cur = head, pred = null, temp = null; while(cur!=null){ temp = cur.next; cur.next = pred; pred = cur; cur = temp; } return pred; } } -
但是，反转链表会破坏原来链表的结构。
- 可以通过记录反转部分的头结点，和前半部分的尾节点，通过再进行一次反转恢复结构。
p.next = reverse(q);
3、其他链表题目()
两数相加
-
直观解法非常简单，就是从后往前对链表中的值相加。
- 需要考虑的一个是只要链表向后遍历的过程中有一个不是null，或者进位不是0，就说明需要新建一个链表节点。
- 优化的话，如果其中一个链表为空并且进位为0了，就可以直接把另一个链表接到新链表后面。
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); int i = 0, add = 0, sum = 0; int v1 = 0, v2 = 0; ListNode curr = head; while(l1!=null || l2!=null || add>0){ if(l1==null){ v1 = 0; } else { v1 = l1.val; l1 = l1.next; } if(l2==null){ v2 = 0; } else { v2 = l2.val; l2 = l2.next; } sum = v1 + v2 + add; add = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; } return head.next; } }
删除链表的倒数第N个节点
-
首先n是有效的，也就是说对n的合法性不需要做判断。
-
一趟扫描就要完成，需要用到多个指针，慢指针del与快指针last相距n-1。
- 因为当n=1时，所要删除的就是最后一个节点。而要删除一个节点，最好使能获取其前一个节点的位置，直接把前一个节点的next指向next.next。
- 然后快慢指针向后遍历，直到快指针的下一个为null，则删除此时慢指针指向的下一个元素。
- 为了好处理快慢指针的初始化和删除链表第一个节点的问题，引入头哨兵header。
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode header = new ListNode(0, head); ListNode del = header, last = header; while(n-->0) { last = last.next; } while(last.next!=null){ last = last.next; del = del.next; } del.next = del.next.next; return header.next; } }
合并两个有序链表
-
迭代思路：
- 首先同样构造一个头哨兵，从头哨兵开始，最后返回头哨兵的next。
- 当l1和l2都不为空的时候向后遍历，比较值的大小。cur指向新链表的尾，l1和l2指向旧链表的头。
- 当有一个为null时，直接将另一个接上就行了。
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode header = new ListNode(0); ListNode cur = header; while(l1!=null && l2!=null){ if(l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if(l1!=null) { cur.next = l1; } else { cur.next = l2; } return header.next; } } -
递归思路：
- 递归基是为null时直接返回。但是因为用到了栈，空间复杂度不如迭代。
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
合并K个升序链表
-
常规想法，每次比较k个链表头的最小值，复杂度等于顺序合并：
class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode header = new ListNode(0); ListNode cur = header; while(true) { ListNode min = null; int temp = -1; for(int i=0; i<lists.length; i++) { if(lists[i]==null) { continue; } else { if(min==null || lists[i].val<min.val) { min = lists[i]; temp = i; } } } if(temp == -1) { break; } cur.next = min; cur = cur.next; lists[temp] = cur.next; } return header.next; } } -
相比于顺序合并两个相邻的链表，分治合并的效率更高。
-
顺序合并：
-
分治合并：
-
分治时要注意，这里的递归基有两个，一个是如果区间lo和hi相等，就返回这个链表的指针。另一个是，如果输入数组为空就返回null。
class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length-1); } ListNode merge(ListNode[] lists, int lo, int hi) { if(lo==hi) { return lists[lo]; } if(lo>hi) { return null; } int mid = (lo+hi)/2; return mergeTwoLists(merge(lists, lo, mid), merge(lists, mid+1, hi)); } ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode header = new ListNode(0); ListNode cur = header; while(l1!=null && l2!=null){ if(l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if(l1!=null) { cur.next = l1; } else { cur.next = l2; } return header.next; } } -
两两交换链表中的节点
-
递归形式，就是反转链表的变种：
- 递归基是如果传入的链表只有一个节点或为null，就直接返回。
- 否则，交换并链接头尾。
class Solution { public ListNode swapPairs(ListNode head) { if(head==null || head.next==null){ return head; } else { ListNode temp = head.next.next, ans = head.next; head.next.next = head; head.next = swapPairs(temp); return ans; } } } -
迭代形式：
- 迭代比较麻烦的就是处理null的问题。
class Solution { public ListNode swapPairs(ListNode head) { if(head==null || head.next==null) return head; ListNode header = new ListNode(0, head), curr = head, tail = head.next.next, temp = null, ans=header; while(true) { temp = curr.next; temp.next = curr; curr.next = tail; header.next = temp; if(tail==null || tail.next==null){ return ans.next; } else { header = header.next.next; curr = tail; tail = tail.next.next; } } } }
旋转链表
-
最需要注意的一点就是，先首尾相连把链表变成环，再移动ans指针。不然的话需要单独处理shift为0的情况：
class Solution { public ListNode rotateRight(ListNode head, int k) { if(head==null || head.next==null) return head; ListNode tail=head, ans=head, temp=null; int len = 1; while(tail.next!=null){ tail = tail.next; len++; } tail.next = head; int shift = len - k % len; while(--shift>0){ ans = ans.next; } temp = ans; ans = ans.next; temp.next = null; return ans; } }
删除链表中的重复元素
-
用递归的方式，每次传入处理好的链表尾和需要删除的链表头。
- 检查链表头是否有重复的，有就删除。如果有的话需要特别注意null值的判定和删除后的指向。
class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode header = new ListNode(0, head); deleteD(header, head); return header.next; } void deleteD(ListNode header, ListNode head) { if(head==null || head.next==null) return; if(head.next!=null && head.val == head.next.val) { while(head.next!=null && head.val == head.next.val) { head = head.next; } header.next = head.next; head = header; } deleteD(head, head.next); } }
删除排序链表中的重复元素
-
与前一道题不同的是，重复的需要留下一个，其实就是把上一道题的header.next = head.next改为header.next = head。
class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while(cur!=null && cur.next!=null) { if(cur.val==cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } }
分隔链表
-
分别用哨兵引出小于x和大于x的链：
class Solution { public ListNode partition(ListNode head, int x) { ListNode header1 = new ListNode(0), header2 = new ListNode(0), cur1 = header1, cur2 = header2; while(head!=null) { if(head.val<x){ cur1.next = head; cur1 = cur1.next; } else { cur2.next = head; cur2 = cur2.next; } head = head.next; } cur1.next = header2.next; cur2.next = null; return header1.next; } }
iwehdio的博客园：https://www.cnblogs.com/iwehdio/