网站logo图怎么做的/深圳seo秘籍
简介
我们平时会发现如果一道题如果涉及数据结构，那么他的算法思路一般相对其它同等难度的题要简单，其实链表也一样，纯链表的题也不会特别难。了解了一些套路之后，做题方法也是有迹可寻，我们可以适当记一些模板，这样可以加快我们解题的速度，比如如何寻找中点，用虚拟节点或递归法反转链表等，其中递归是链表篇的重点，其实也整个刷题生涯中的重点，链表中的递归，回溯中的递归，二叉树和图中的递归等等，所以这里也会讲一下递归的书写模板，要重点学习。
理论基础
链表是一种线性存储结构，采用的是链式存储。可以采用连续的存储空间，也可以采用零散的非连续存储空间。 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表示意图如下：
除了以上这种单链表以外，还有双向链表和循环链表。在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点指向前一个结点，构成一个链表，就产生了双向链表的概念了。即每个节点都有两个指针。双向链表示意图如下：
循环链表其实也好理解，就是首尾节点连接在一起了罢了，我们平时写链表代码时，如非必要，要注意循环链表的产生，否则可能会导致CPU空转，出现致命BUG，循环链表示意图如下：
链表的特点
- 是一种线性存储结构。
- 节点值包含两部分，分别为数据域和指针域。
- 可以采用零散的存储空间。
- 和数组相比，内存消耗更大，主要需要多存一个指针域。
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。
- 和数组比，无固定长度，理论上来讲，只要内存没爆，能一直存。
- 线性链表还可分为单链表，双向链表，循环链表等。
- 链表节点的增加一般有头插入法和尾插入法两种。
链表类的定义：
public class ListNode {// 结点的值int val;// 下一个结点ListNode next;// 节点的构造函数(无参)public ListNode() {}// 节点的构造函数(有一个参数)public ListNode(int val) {this.val = val;}// 节点的构造函数(有两个参数)public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}
解题方式
解链表的题，一定要会两招，一招是递归，一招是迭代法。其中递归的写法可以分成三步走：
-
一、明确函数功能： 要清楚你写这个函数是想要做什么。
-
二、寻找递归出口： 递归一定要有结束条件，不然会永远递归下去，禁止套娃。
-
三、找出递推关系： 开始实现递归，一步一步递推出最终结果。
递归方式主要在链表反转时，或者需要从后往前操作链表时，经常用到，写递归函数时，一定要明确递推关系和递归出口，否则不可能写好递归的。至于迭代法，其实不过就是写循环，一般比递归要好理解一些，代码也更好写，但有的题不能直接看出来用迭代法，但请相信：所有的递归都可以用循环来写。接下来看一下递归和迭代的模板：// 递归模板 class Solution {public BBB AAA(ListNode head) {return helper(入参);}private BBB helper(入参) {if (终止条件) {return xxx;}// 函数功能return helper(参数); # 递归调用} }// 迭代模板 ... 其实就是 for 或 while 循环 ...for(...){... ...}while(...){... ...}下面以反转链表这题经典题，来展示这两种方法。
// 递归法反转链表 class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);} }// 迭代法反转链表 class Solution {public ListNode reverseList(ListNode head) {// 申请新虚拟节点ListNode dummy = new ListNode(0);ListNode p = dummy, cur = head;while(cur != null){// 从head摘下一个头ListNode t = cur;cur = cur.next; // cur移到下一个t.next = p.next; // 头插法插入，依次反转p.next = t;}return dummy.next;} }
以上迭代法的书写方式，也可以叫做虚拟头节点法，相当于递归来说，更易于我们理解。链表的题，有时申请一个虚拟头节点，题解就会豁然开朗。
解题心得
- 只要弄清链表的特性，单纯的链表题一般也不难。
- 一定要学会几种反转链表的方式，很重要。
- 递归一定要好好学习，无论是链表题，还是之后的题，都会经常用到，最好能理解并默写模板。
- 寻找链表中点，只需要用双指针，Slow前行一步，Fast前行两步，Fast到底，Slow就是中间节点了。
- 在leetcode中通常链表已经定义好了，但我们平时也要注意链表类的定义怎么写，因为面试时，是不会有人给你定义的，这些都需要你自己写。
算法题目
2. 两数相加
题目解析：将两链表直接相加，要注意进位（carry）的处理，这里可以用虚拟头节点来处理链表，会更方便。
代码如下：
/*** Definition for singly-linked list.* public caass ListNode {* int bal;* ListNodeint val; 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) {// 声明一个虚拟头节点ListNode dummyHead = new ListNode(0);ListNode curr = dummyHead;int carry = 0;// 只要有一个链表不为空，则需继续相加while(l1 != null || l2 != null){int a = (l1 != null) ? l1.val : 0;int b = (l2 != null) ? l2.val : 0;int sum = carry + a + b;// 无进位，则carry为零carry = sum / 10;// 节点值为个位数数值curr.next = new ListNode(sum % 10);curr = curr.next;if(l1 != null ) l1 = l1.next;if(l2 != null ) l2 = l2.next;}// 若最后有进位，则新加一个节点if(carry > 0){curr.next = new ListNode(carry);}return dummyHead.next;}
}
24. 两两交换链表中的节点
题目解析：递归整个链表，然后按两两相交的规则，重新生成新链表。
代码如下：
/*** 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) {return swap(head);}public ListNode swap(ListNode head){if(head == null || head.next == null){return head;}ListNode tampA = head;ListNode tampB = head.next.next;// 按新链表的生成顺序，完成代码书写，更便于理解head = head.next;head.next = tampA;head.next.next = swap(tampB);return head;}
}
25. K 个一组翻转链表
题目解析：这里需要双重递归，每过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) {// 新的headListNode newHead = head;// 运行至该节点ListNode tempA = head;for (int i = 0; i < k; i++) {if (tempA == null) {return head;}if (i == k - 1) {newHead = tempA;}tempA = tempA.next;}// 反转后的最后一个节点ListNode tempB = reverse(head, k);// 当前段最后一个节点与下一段开头相连tempB.next = reverseKGroup(tempA, k);return newHead;}/*** 用递归反转链表*/public ListNode reverse(ListNode head, int k) {if (k == 1) {return head;}ListNode newHead = reverse(head.next, --k);newHead.next = head;return newHead.next;}
}
83. 删除排序链表中的重复元素
题目解析：直接遍历全链表，有重复删除即可。
代码如下：
/*** 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) {ListNode res = head;while (head != null && head.next != null) {if (head.val == head.next.val) {head.next = head.next.next;} else {head = head.next;}}return res;}
}
92. 反转链表 II
题目解析：用递归反转指定范围里的节点，再连接进主链表即可。
代码如下：
/*** 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 {ListNode successor = null;public ListNode reverseBetween(ListNode head, int left, int right) {if (left == 1) {return helper(head, right);}head.next = reverseBetween(head.next, left - 1, right - 1);return head;}public ListNode helper(ListNode head, int n) {if (n == 1) {successor = head.next;return head;}ListNode last = helper(head.next, n - 1);head.next.next = head;head.next = successor;return last;}
}
155. 最小栈
题目解析：用链表，每个节点存储时，把该节点情况下最小值也存进去即可。
代码如下：
/*** 链表*/
class MinStack {private Node head;public void push(int x) {if(head == null) head = new Node(x, x);else head = new Node(x, Math.min(x, head.min), head);}public void pop() {head = head.next;}public int top() {return head.val;}public int getMin() {return head.min;}private class Node {int val;int min;Node next;private Node(int val, int min) {this(val, min, null);}private Node(int val, int min, Node next) {this.val = val;this.min = min;this.next = next;}}
}
/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/
203. 移除链表元素
题目解析：虚拟头节点，用虚拟头节点的好处是，防止第一个节点也是删除的节点的情况，且方便返回头节点。
代码如下：
/*** 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 removeElements(ListNode head, int val) {ListNode header = new ListNode(-1);header.next = head;ListNode cur = header;while(cur.next != null){// 当前节点下一节点为删除节点时，直接删除掉下一节点if(cur.next.val == val ){cur.next = cur.next.next;}else{cur = cur.next;}}return header.next;}
}
206. 反转链表
题目解析：虚拟头节点，用虚拟头节点方便返回头节点。
代码如下：
/*** 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){return null;}ListNode dummyHead = new ListNode(-1);while(head != null){ListNode temp = dummyHead.next;dummyHead.next = new ListNode(head.val);dummyHead.next.next = temp;head = head.next;}return dummyHead.next;}
}
237. 删除链表中的节点
题目解析：依次用后一节点的值代替当前节点的值。
代码如下：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*//*** 链表*/
class Solution {public void deleteNode(ListNode node) {// 今当前节点值为下一节点值node.val = node.next.val;// 申请下一节点ListNode nextNode = node.next;// 判断依次替换之后的节点while (nextNode.next != null) {nextNode.val = nextNode.next.val;node = nextNode;nextNode = nextNode.next;}// 删除最后一个节点node.next = null;}
}
回到首页
刷 leetcode 500+ 题的一些感受
下一篇
《算法系列》之哈希表