## 力扣链表+简单递归 转

o
osc_gu9d45li

#链表算法 https://leetcode-cn.com/problemset/all/?topicSlugs=linked-list&difficulty=%E7%AE%80%E5%8D%95 ----题目链接 ##1.设计链表 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

``````     class Node {
int val;
Node next;
Node(int x) { this.val = x; }
}
int size=0;

/** Initialize your data structure here. */

}

/** 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;
}
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. */
size++;
Node node =new Node(val);
tail=node;
}
}

/** Append a node of value val to the last element of the linked list. */
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;
}
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--;
while(index>0){
index--;
curr=curr.next;
}
if(curr.next!=null)
{
curr.next=curr.next.next;
}
if(curr.next == null){
tail =curr;
}

}
}
``````

###解析 还是蛮基础、蛮实用的。不是很难看一看就会了

##2.回文链表 请判断一个链表是否为回文链表。

###代码 /** * 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.删除链表中的节点 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

``````}
``````

##4.链表中间节点

###代码

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {

while(fast.next!=null)
{
slow=slow.next;

if(fast.next.next==null)
{
fast=fast.next;

}
else{
fast=fast.next.next;

}

}

return slow;

}
}
``````

###解析 快慢指针，一个二倍速，很简单啦

##4..合并两个有序队列（java)

###代码

``````	/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
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;
}
}
}
``````

##解析

1. 这已经是一个排好序的队列了，两个队列如果都不空，就谁更小谁进入新的链表。最后剩下的一条不空链表一定是有序的接在新链表的尾部即可（也一定是大于前面的元素）

##5.相交链表

###代码 /** * 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;
if(n<m){
l=m-n;

}
else{
l=n-m;
}

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;
}
}
``````

###解析

1. 链表为空一定没有相交的，返回null
2. 遍历两个链表的长度（如果末尾的元素不等也返回NULL)，削短长度长的链表使两个链表等长。
3. 一次遍历两个链表，如果地址相同，则是相交的点。（注意不是链表节点的值相同，而是地址相同）。返回节点即可 #递归接替三部曲

1. 整个递归的终止条件。

2. 一级递归需要做什么？

3. 应该返回给上一级的返回值是什么？

1. 找整个递归的终止条件：递归应该在什么时候结束？

2. 找返回值：应该给上一级返回什么信息？

3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？

###代码

``````	/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
{
}
{
}
else {
}

}
}
``````

###解析

2. 想想应该返回什么值：应该返回的自然是已经去重的链表的头节点

##7.删除链表元素

###题目 删除链表中等于给定值 val 的所有节点。

``````	/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
}
}
}
``````

##8.反转链表 ###题目 反转一个单链表。

``````class Solution {

{

}

return p;
}
}
``````

##9.二叉树深度

###代码 /** * 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;

}
}
``````

###解析 求二叉树的最大深度，那么直接套递归解题三部曲模版：

1. 找终止条件。 什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。

2. 找返回值。 应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。

3. 本级递归应该做什么。 首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，看下图。此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。

##10.两两相交链表的节点

###代码 /** * 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; } }

###解析

1. 找终止条件。 什么情况下递归终止？没得交换的时候，递归就终止了呗。因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。

2. 找返回值。 我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。

##11.平衡二叉树

###代码 /** * 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. 找终止条件。 什么情况下递归应该终止？自然是子树为空的时候，空树自然是平衡二叉树了。

2. 应该返回什么信息：

``````class ReturnNode{
boolean isB;
int depth;
//构造方法
public ReturnNode(boolean isB, int depth){
this.isB = isB;
this.depth = depth;
}
}
``````
1. 本级递归应该做什么。 知道了第二步的返回值后，这一步就很简单了。目前树有三个节点：root，left，right。我们首先判断left子树和right子树是否是平衡二叉树，如果不是则直接返回false。再判断两树高度差是否不大于1，如果大于1也直接返回false。否则说明以root为节点的子树是平衡二叉树，那么就返回true和它的高度。

o

### osc_gu9d45li

SQLServer实现split分割字符串到列

cwalet
2014/05/21
9.5K
0

SQLScreens 是一个使用 Tcl/TK 编写的简单关系型数据库表单生成工具。可让你快速创建查询界面，并指定相应的表和字段。支持多种数据库，包括：MySQL, SQLite, and INFORMIX, and ODBC for o...

2013/02/17
848
0
N简单CMS

N简单CMS能够让网站开发者更快速、灵活、简单的开发网站。 N简单CMS有以下特点： 更简单和自由的模板标签调用 专注于人性化的管理和操作 基于完全php5框架Kohana2.3.4开发 资源调用和消耗更低...

2013/02/26
3.1K
0

2013/03/12
2.5K
0

leehorsley
2012/10/22
1.6K
0

46
0
HTML中id属性的有效值是什么？ - What are valid values for the id attribute in HTML?

25
0
mysql innodb 可重复 幻读问题

1 mvcc 解决快照读幻读 2 GAP 锁解决 当前读幻读 (insert时 插入意向锁会等待GAP锁)

yzzzzzzzz

25
0

07/31
16
0
2020年TOP7的编程语言和框架，它们至少还能风靡全球5年以上

25
0