链表算法
https://leetcode-cn.com/problemset/all/?topicSlugs=linked-list&difficulty=简单 ----题目链接
1.设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
代码
class MyLinkedList {
class Node {
int val;
Node next;
Node(int x) { this.val = x; }
}
int size=0;
private Node head =new Node(0);//头节点，
private Node tail=head;//尾结点
/** Initialize your data structure here. */
public MyLinkedList() {
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index <0 || index >=size){
return -1;
}
Node curr =head;
while(index>=0){
index--;
curr=curr.next;
}
return curr.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
size++;
Node node =new Node(val);
node.next =head.next;
head.next =node;
if(tail == head){//尾结点（只有一个节点的时候）
tail=node;
}
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
size++;
Node node = new Node(val);
tail.next =node;
tail =tail.next;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if(index>size){
return;
}
size++;
Node node= new Node(val);
if(index==size-1){
tail.next=node;
tail=tail.next;
return;
}
Node curr =head;
while(index>0){
index--;
curr =curr.next;
}
node.next =curr.next;
curr.next=node;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index<0 || index>=size){
return;
}
size--;
Node curr=head;
while(index>0){
index--;
curr=curr.next;
}
if(curr.next!=null)
{
curr.next=curr.next.next;
}
if(curr.next == null){
tail =curr;
}
}
}
解析
还是蛮基础、蛮实用的。不是很难看一看就会了
2.回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
boolean isPalindrome(ListNode head) {
ListNode slow =head;ListNode fast =head;ListNode prev = null;
while(fast!=null){
slow=slow.next;
if(fast.next !=null) fast=fast.next.next;
else fast=fast.next;
}
while(slow!=null){
//反转
ListNode ovn =slow.next;
slow.next =prev;
prev= slow;
slow=ovn;
}
while(head!=null && prev!=null)
{
//check
if(head.val != prev.val)
{
return false;
}
head =head.next;
prev =prev.next;
}
return true;
}
}
解析
其一，find mid node 使用快慢指针找到链表中点。 其二，reverse 逆序后半部分。 其三，check 从头、中点，开始比较是否相同。
3.删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
代码
/**
* 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;
node.next=node.next.next;
}
}
解析：很精巧的一道题，参数没有给head一开始没注意到。
4.链表中间节点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast.next!=null)
{
slow=slow.next;
if(fast.next.next==null)
{
fast=fast.next;
}
else{
fast=fast.next.next;
}
}
return slow;
}
}
解析
快慢指针，一个二倍速，很简单啦
4..合并两个有序队列（java)
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode Newhead = new ListNode(0);
ListNode newl = Newhead;
while(l1!=null && l2!=null){
if(l1.val<=l2.val)
{
newl.next=l1;
l1=l1.next;
newl=newl.next;
}
else
{
newl.next=l2;
l2=l2.next;
newl=newl.next;
}
}
if(l1 == null)
{
newl.next=l2;
}
else{
newl.next=l1;
}
return Newhead.next;
}
}
解析
- 这已经是一个排好序的队列了，两个队列如果都不空，就谁更小谁进入新的链表。最后剩下的一条不空链表一定是有序的接在新链表的尾部即可（也一定是大于前面的元素）
- 最后要返回一整条链表，发现定义的new1的指针指在了链表的中部，所以在一开始定义的时候一定要留有一个指向链表头部的Newhead,这样才能返回一个完整的链表
5.相交链表
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
int m=0,n=0;
if(a ==null ||b ==null ) return null;
while(a.next!= null){
++m;
a=a.next;
}
while(b.next!=null)
{
++n;
b=b.next;
}
if(a !=b) return null;
int i=0,l=0;
a=headA;
b=headB;
if(n<m){
l=m-n;
}
else{
l=n-m;
a=headB;
b=headA;
}
while(i<l){
a=a.next;
i++;
}
while(a!=null && b!= null)
{
if(a== b) return a;
a=a.next;
b=b.next;
// System.out.println(a.val);
// System.out.println(b.val);
}
return null;
}
}
解析
- 链表为空一定没有相交的，返回null
- 遍历两个链表的长度（如果末尾的元素不等也返回NULL)，削短长度长的链表使两个链表等长。
- 一次遍历两个链表，如果地址相同，则是相交的点。（注意不是链表节点的值相同，而是地址相同）。返回节点即可
递归接替三部曲
何为递归？程序反复调用自身即是递归。
我自己在刚开始解决递归问题的时候，总是会去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么…然后就会觉得实现一个递归解法十分复杂，根本就无从下手。
相信很多初学者和我一样，这是一个思维误区，一定要走出来。既然递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
我们需要关心的主要是以下三点：
-
整个递归的终止条件。
-
一级递归需要做什么？
-
应该返回给上一级的返回值是什么？
因此，也就有了我们解树形递归题的三部曲：
-
找整个递归的终止条件：递归应该在什么时候结束？
-
找返回值：应该给上一级返回什么信息？
-
本级递归应该做什么：在这一级递归中，应该完成什么任务？
一定要理解这3步，这就是以后递归秒杀算法题的依据和思路。
但这么说好像很空，我们来以题目作为例子，看看怎么套这个模版，相信3道题下来，你就能慢慢理解这个模版。之后再解这种套路递归题都能直接秒了。
6.删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next ==null )
{
return head;
}
head.next = deleteDuplicates(head.next);
if(head.val == head.next.val)
{
return head.next;
}
else {
return head;
}
}
}
解析
递归套路解决链表问题：
- 找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
- 想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
- 每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head
7.删除链表元素
题目
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
head.next=removeElements(head.next,val);
if(head.val ==val){
return head.next;
}
else return head;
}
}
解析：暂无
8.反转链表
题目
反转一个单链表。
示例:
输入: 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(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
{
return head;
}
ListNode p =reverseList(head.next);
head.next.next=head;
head.next =null;
return p;
}
}
9.二叉树深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
tupian------------------
返回它的最大深度 3 。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root ==null)
{
return 0;
}
int Deepleft = maxDepth(root.left);
int DeepRight = maxDepth(root.right);
return Math.max(Deepleft,DeepRight)+1;
}
}
解析
求二叉树的最大深度，那么直接套递归解题三部曲模版：
-
找终止条件。 什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。
-
找返回值。 应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。
-
本级递归应该做什么。 首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，看下图。此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。
10.两两相交链表的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next ==null)
{
return head;
}
ListNode next =head.next;
head.next = swapPairs(next.next);
next .next =head;
return next;
}
}
解析
直接上三部曲模版：
-
找终止条件。 什么情况下递归终止？没得交换的时候，递归就终止了呗。因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。
-
找返回值。 我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。
-
本级递归应该做什么。 结合第二步，看下图！由于只考虑本级递归，所以这个链表在我们眼里其实也就三个节点：head、head.next、已处理完的链表部分。而本级递归的任务也就是交换这3个节点中的前两个节点，就很easy了。
11.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private class ReturnNode{
//这个ReturnNode是参考我描述的递归套路的第二步：思考返回值是什么
//一棵树是BST等价于它的左、右俩子树都是BST且俩子树高度差不超过1
//因此我认为返回值应该包含当前树是否是BST和当前树的高度这两个信息
boolean isB;
int depth;
public ReturnNode(int depth,boolean isB){
this.isB = isB;
this.depth = depth;
}
}
//主函数
public boolean isBalanced(TreeNode root) {
return isBST(root).isB;
}
//参考递归套路的第三部：描述单次执行过程是什么样的
//这里的单次执行过程具体如下：
//是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值
public ReturnNode isBST(TreeNode root){
if(root == null){
return new ReturnNode(0,true);
}
//不平衡的情况有3种：左树不平衡、右树不平衡、左树和右树差的绝对值大于1
ReturnNode left = isBST(root.left);
ReturnNode right = isBST(root.right);
if(left.isB == false || right.isB == false){
return new ReturnNode(0,false);
}
if(Math.abs(left.depth - right.depth)> 1){
return new ReturnNode(0,false);
}
//不满足上面的三种情况，说明平衡了，树的深度为左右子树的最大深度+1;
return new ReturnNode(Math.max(left.depth,right.depth)+1,true);
}
}
解析
-
找终止条件。 什么情况下递归应该终止？自然是子树为空的时候，空树自然是平衡二叉树了。
-
应该返回什么信息：
为什么我说这个题是集合了模版精髓？正是因为此题的返回值。要知道我们搞这么多花里胡哨的，都是为了能写出正确的递归函数，因此在解这个题的时候，我们就需要思考，我们到底希望返回什么值？
何为平衡二叉树？平衡二叉树即左右两棵子树高度差不大于1的二叉树。而对于一颗树，它是一个平衡二叉树需要满足三个条件：它的左子树是平衡二叉树，它的右子树是平衡二叉树，它的左右子树的高度差不大于1。换句话说：如果它的左子树或右子树不是平衡二叉树，或者它的左右子树高度差大于1，那么它就不是平衡二叉树。
而在我们眼里，这颗二叉树就3个节点：root、left、right。那么我们应该返回什么呢？如果返回一个当前树是否是平衡二叉树的boolean类型的值，那么我只知道left和right这两棵树是否是平衡二叉树，无法得出left和right的高度差是否不大于1，自然也就无法得出root这棵树是否是平衡二叉树了。而如果我返回的是一个平衡二叉树的高度的int类型的值，那么我就只知道两棵树的高度，但无法知道这两棵树是不是平衡二叉树，自然也就没法判断root这棵树是不是平衡二叉树了。
因此，这里我们返回的信息应该是既包含子树的深度的int类型的值，又包含子树是否是平衡二叉树的boolean类型的值。可以单独定义一个ReturnNode类，如下：
class ReturnNode{
boolean isB;
int depth;
//构造方法
public ReturnNode(boolean isB, int depth){
this.isB = isB;
this.depth = depth;
}
}
- 本级递归应该做什么。 知道了第二步的返回值后，这一步就很简单了。目前树有三个节点：root，left，right。我们首先判断left子树和right子树是否是平衡二叉树，如果不是则直接返回false。再判断两树高度差是否不大于1，如果大于1也直接返回false。否则说明以root为节点的子树是平衡二叉树，那么就返回true和它的高度。