Java面向对象是什么意思?

　　Java是一种面向对象的程序设计语言，了解面向对象的编程思想对于学习Java开发相当重要。下面叩丁狼学院就为大家介绍介绍什么是java面向对象思想。

　　1、面向对象的概念

　　面向对象是一种符合人类思维习惯的编程思想。现实生活中存在各种形态不同的事物，这些事物之间存在着各种各样的联系。在程序中使用对象来映射现实中的事物使用对象的关系来描述事物之间的联系，这种思想就是面向对象。

　　提到面向对象，自然会想到面向过程，面向过程就是分析解决问题所需要的步骤，然后用函数把这些步骤一一实现，使用的时候一个一个依次调用就可以了。面向对象则是把解决的问题按照一定规则划分为多个独立的对象，然后通过调用对象的方法来解决问题。当然，一个应用程序会包含多个对象，通过多个对象的相互配合来实现应用程序的功能，这样当应用程序功能发生变动时，只需要修改个别的对象就可以了，从而使代码更容易得到维护。

　　2、面向对象的特点

　　面向对象的特点主要可以概括为封装性、继承性和多态性，接下来针对这三种特性进行简单介绍。



　　封装性

　　封装是面向对象的核心思想，将对象的属性和行为封装起来，不需要让外界知道具体实现细节，这就是封装思想。例如，用户使用电脑，只需要使用手指敲键盘就可以了无须知道电脑内部是如何工作的，即使用户可能碰巧知道电脑的工作原理，但在使用时，并不完全依赖电脑工作原理这些细节。

　　继承性

　　继承性主要描述的是类与类之间的关系，通过继承，可以在无须重新编写原有类的情况下，对原有类的功能进行扩展。例如，有一个汽车的类，该类中描述了汽车的普通特性和功能，而轿车的类中不仅应该包含汽车的特性和功能，还应该增加轿车特有的功能，这时，可以让轿车类继承汽车类，在轿车类中单独添加轿车特性的方法就可以了。继承性不仅增强了代码复用性，提高了开发效率，而且为程序的修改补充提供了便利。

　　多态性

　　多态性指的是在程序中允许出现重名现象，它指在一个类中定义的属性和方法被其他类继承后，它们可以具有不同的数据类型或表现出不同的行为，这使得同一个属性和方法在不同的类中具有不同的语义。例如，当听到 Cut 这个单词时，理发师的行为是剪发，演员的行为是停止表演不同的对象，所表现的行为是不一样的。

　　想要真正理解Java面向对象的思想光靠上面的介绍是不过，需要通过大量的实践去学习和理解，才能将面向对象真正领悟。想要系统学习java编程，就到叩丁狼学院。



 

1 问题分析:

dubbo 的 spi 思想是什么？

继续深入问呗，前面一些基础性的东西问完了，确定你应该都 ok，了解 dubbo 的一些基本东西，那么问个稍微难一点点的问题，就是 spi，先问问你 spi 是啥？然后问问你 dubbo 的 spi 是怎么实现的？

其实就是看看你对 dubbo 的掌握如何。

2 面试题回答:

spi 是啥？

spi，简单来说，就是 service provider interface，说白了是什么意思呢，比如你有个接口，现在这个接口有 3 个实现类，那么在系统运行的时候对这个接口到底选择哪个实现类呢？这就需要 spi 了，需要根据指定的配置或者是默认的配置，去找到对应的实现类加载进来，然后用这个实现类的实例对象。

举个栗子。

你有一个接口 A。A1/A2/A3 分别是接口A的不同实现。你通过配置 接口 A = 实现 A2，那么在系统实际运行的时候，会加载你的配置，用实现 A2 实例化一个对象来提供服务。

spi 机制一般用在哪儿？插件扩展的场景，比如说你开发了一个给别人使用的开源框架，如果你想让别人自己写个插件，插到你的开源框架里面，从而扩展某个功能，这个时候 spi 思想就用上了。

Java spi 思想的体现

spi 经典的思想体现，大家平时都在用，比如说 jdbc。

Java 定义了一套 jdbc 的接口，但是 Java 并没有提供 jdbc 的实现类。

但是实际上项目跑的时候，要使用 jdbc 接口的哪些实现类呢？一般来说，我们要根据自己使用的数据库，比如 mysql，你就将 mysql-jdbc-connector.jar 引入进来；oracle，你就将 oracle-jdbc-connector.jar 引入进来。

在系统跑的时候，碰到你使用 jdbc 的接口，他会在底层使用你引入的那个 jar 中提供的实现类。

dubbo 的 spi 思想

dubbo 也用了 spi 思想，不过没有用 jdk 的 spi 机制，是自己实现的一套 spi 机制。

Protocol protocol = ExtensionLoader.getExtensionLoader(Protocol.class).getAdaptiveExtension();

Protocol 接口，在系统运行的时候，，dubbo 会判断一下应该选用这个 Protocol 接口的哪个实现类来实例化对象来使用。

它会去找一个你配置的 Protocol，将你配置的 Protocol 实现类，加载到 jvm 中来，然后实例化对象，就用你的那个 Protocol 实现类就可以了。

上面那行代码就是 dubbo 里大量使用的，就是对很多组件，都是保留一个接口和多个实现，然后在系统运行的时候动态根据配置去找到对应的实现类。如果你没配置，那就走默认的实现好了，没问题。

@SPI("dubbo")  
public interface Protocol {  
      
    int getDefaultPort();  
  
    @Adaptive  
    <T> Exporter<T> export(Invoker<T> invoker) throws RpcException;  
  
    @Adaptive  
    <T> Invoker<T> refer(Class<T> type, URL url) throws RpcException;  

    void destroy();  
  
}  

在 dubbo 自己的 jar 里，在/META_INF/dubbo/internal/com.alibaba.dubbo.rpc.Protocol文件中：

dubbo=com.alibaba.dubbo.rpc.protocol.dubbo.DubboProtocol
http=com.alibaba.dubbo.rpc.protocol.http.HttpProtocol
hessian=com.alibaba.dubbo.rpc.protocol.hessian.HessianProtocol

所以说，这就看到了 dubbo 的 spi 机制默认是怎么玩儿的了，其实就是 Protocol 接口，@SPI("dubbo") 说的是，通过 SPI 机制来提供实现类，实现类是通过 dubbo 作为默认 key 去配置文件里找到的，配置文件名称与接口全限定名一样的，通过 dubbo 作为 key 可以找到默认的实现类就是 com.alibaba.dubbo.rpc.protocol.dubbo.DubboProtocol。

如果想要动态替换掉默认的实现类，需要使用 @Adaptive 接口，Protocol 接口中，有两个方法加了 @Adaptive 注解，就是说那俩接口会被代理实现。

啥意思呢？

比如这个 Protocol 接口搞了俩 @Adaptive 注解标注了方法，在运行的时候会针对 Protocol 生成代理类，这个代理类的那俩方法里面会有代理代码，代理代码会在运行的时候动态根据 url 中的 protocol 来获取那个 key，默认是 dubbo，你也可以自己指定，你如果指定了别的 key，那么就会获取别的实现类的实例了。

如何自己扩展 dubbo 中的组件

下面来说说怎么来自己扩展 dubbo 中的组件。

自己写个工程，要是那种可以打成 jar 包的，里面的 src/main/resources 目录下，搞一个 META-INF/services，里面放个文件叫：com.alibaba.dubbo.rpc.Protocol，文件里搞一个my=com.bingo.MyProtocol。自己把 jar 弄到 nexus 私服里去。

然后自己搞一个 dubbo provider 工程，在这个工程里面依赖你自己搞的那个 jar，然后在 spring 配置文件里给个配置：

<dubbo:protocol name=”my” port=”20000” />

provider 启动的时候，就会加载到我们 jar 包里的my=com.bingo.MyProtocol 这行配置里，接着会根据你的配置使用你定义好的 MyProtocol 了，这个就是简单说明一下，你通过上述方式，可以替换掉大量的 dubbo 内部的组件，就是扔个你自己的 jar 包，然后配置一下即可。



dubbo 里面提供了大量的类似上面的扩展点，就是说，你如果要扩展一个东西，只要自己写个 jar，让你的 consumer 或者是 provider 工程，依赖你的那个 jar，在你的 jar 里指定目录下配置好接口名称对应的文件，里面通过 key=实现类。

然后对于对应的组件，类似 <dubbo:protocol> 用你的那个 key 对应的实现类来实现某个接口，你可以自己去扩展 dubbo 的各种功能，提供你自己的实现。

数据库中的游标到底是什么意思
关注:177  答案:2  mip版
解决时间 2021-01-15 20:54
提问者更无风月
2021-01-15 15:53
数据库中的游标到底是什么意思
最佳答案
二级知识专家癡情菂尐豬豬
2021-01-15 16:47
游标用于按顺序遍历结果集。但一般情况下，应尽量避免使用游标。原因：1. 游标违背了关系模型，即按集合来考虑问题的思想；2. 游标逐行对纪录进行操作，会带来额外的开销，使用游标的解决方案通常比使用集合的解决方案要慢得多；3. 使用游标的解决方案，需要用很多代码来描述对游标的操作，因此代码更长，可读性更差，也更难以维护。
只有在少数情况下才应当使用游标。举两个例子：1. 需要遍历表名，进行DDL操作；2. 连续聚合，此时基于游标的解决方案可能比基于集合的解决方案更快。
全部回答
1楼凊搽蒗囝
2021-01-15 18:27
你是指asp里面的数据库连接组件里面所属记录集的游标吧?
如conn,1,1后面的参数什么的.
简单说来:
conn,1,1为只读数据；1,3为插入数据；2,3是修改数据
游标的意思形象的说一个表格里有许多行数据，我用鼠标指向某一行数据(在asp里面叫记录集)你可以拖用鼠标指向下一行。在asp里面同样也可以。不过要通过它：rs.movenext，记录集往下移。
至于具体和理论知识如下：
游标类型
const adopenforwardonly = 0
前向游标，为缺省游标，提供最快的运行性能。用它打开recordset，从对至尾顺序取得所有结果。它不支持向后滚动，只允许在结果间单向移动。
const adopenkeyset = 1
静态游标，反映第一次打开游标时表中数据的状态，游标无法查明底层表中的数据行是否更新过、删除过或添加了新的数据。不过与只能前移的洲标不同，静态游标可以在结果间前后滚动。
const adopendynamic = 2
键盘驱动的游标，可以查询表中底层数据行的某些变化，但不是全部。它特别是可以准确反映数据是否更新过。但它不能查明其它用户是否曾删除过数据行(删除掉的数据行在recordset中会留下空洞)。键盘驱动的游标支持在结果间前后滚动。
const adopenstatic = 3
动态游标，是最丰富的游标类型。游标打开时可以查询其他用户对表的任何改动，而且支持滚动。
加锁类型
const adlockreadonly = 1
缺省的上锁类型，只读方式上锁允许多个用户同时读取同样的数据，但不能改变数据。
const adlockpessimistic = 2
以悲观上锁方式打开数据对象。该方式假定在你编辑记录时会有其它用户访问数据。此时一旦你开始编辑记录，其它用户就不能访问该数据。
const adlockoptimistic = 3
以乐观上锁方式打开数据对象。该方式假定在你编辑记录时不会有其它用户访问数据。在完成改变之前，其它用户不能访问该记录。
const adlockbatchoptimistic = 4
执行多行批处理更新时使用这种类型
我要举报
如果感觉以上信息为低俗/不良/侵权的信息，可以点下面链接进行举报，我们会做出相应处理，感谢你的支持！
点此我要举报以上信息！
推荐资讯
大家都在看

	

1 引言 
单链表的操作算法是笔试面试中较为常见的题目。本文将着重介绍平时面试中常见的关于链表的应用题目。
本文大概 一万五千字 ，建议阅读时间为一个小时，请先收藏再阅读，平时也可以拿出来多看几遍。
2 输出单链表倒数第 K 个节点 
2.1 问题描述
题目：输入一个单链表，输出此链表中的倒数第 K 个节点。(去除头结点，节点计数从 1 开始)。
2.2 两次遍历法
2.2.1 解题思想
(1)遍历单链表，遍历同时得出链表长度 N 。
(2)再次从头遍历，访问至第 N - K 个节点为所求节点。
2.2.2 图解过程
2.2.3 代码实现
/*计算链表长度*/
int listLength(ListNode* pHead){
    int count = 0;
    ListNode* pCur = pHead->next;
    if(pCur == NULL){
        printf("error");
    }
    while(pCur){
        count++;
        pCur = pCur->pNext;
    }
    return count;
}
/*查找第k个节点的值*/
ListNode* searchNodeK(ListNode* pHead, int k){
    int i = 0;
    ListNode* pCur = pHead; 
    //计算链表长度
    int len = listLength(pHead);
    if(k > len){
        printf("error");
    }
    //循环len-k+1次
    for(i=0; i 1; i++){
        pCur  = pCur->next;
    }
    return pCur;//返回倒数第K个节点
}    
采用这种遍历方式需要两次遍历链表，时间复杂度为O(n※2)。可见这种方式最为简单,也较好理解，但是效率低下。
2.3 递归法
2.3.1 解题思想
(1)定义num = k
(2)使用递归方式遍历至链表末尾。
(3)由末尾开始返回，每返回一次 num 减 1
(4)当 num 为 0 时，即可找到目标节点
2.3.2 图解过程
2.3.3 代码实现
int num;//定义num值
ListNode* findKthTail(ListNode* pHead, int k) {
        num = k;
        if(pHead == NULL)
            return NULL;
        //递归调用
        ListNode* pCur = findKthTail(pHead->next, k);
        if(pCur != NULL)
            return pCur;
        else{
            num--;// 递归返回一次，num值减1
            if(num == 0)
                return pHead;//返回倒数第K个节点
            return NULL;
        }
}
使用递归的方式实现仍然需要两次遍历链表，时间复杂度为O(n※2)。
2.4 双指针法
2.4.1 解题思想
(1)定义两个指针 p1 和 p2 分别指向链表头节点。
(2)p1 前进 K 个节点，则 p1 与 p2 相距 K 个节点。
(3)p1，p2 同时前进，每次前进 1 个节点。
(4)当 p1 指向到达链表末尾，由于 p1 与 p2 相距 K 个节点，则 p2 指向目标节点。
2.4.2 图解过程
2.4.3 代码实现
ListNode* findKthTail(ListNode *pHead, int K){
    if (NULL == pHead || K == 0)
        return NULL;
    //p1，p2均指向头节点
    ListNode *p1 = pHead;
    ListNode *p2 = pHead;
    //p1先出发，前进K个节点
    for (int i = 0; i         if (p1)//防止k大于链表节点的个数
            p1 = p1->_next;
        else
            return NULL;
    }

    while (p1)//如果p1没有到达链表结尾，则p1，p2继续遍历
    {
        p1 = p1->_next;
        p2 = p2->_next;
    }
    return p2;//当p1到达末尾时，p2正好指向倒数第K个节点
}
可以看出使用双指针法只需遍历链表一次，这种方法更为高效时间复杂度为O(n)，通常笔试题目中要考的也是这种方法。
3 链表中存在环问题 
3.1 判断链表是否有环
单链表中的环是指链表末尾的节点的 next 指针不为 NULL ，而是指向了链表中的某个节点，导致链表中出现了环形结构。
链表中有环示意图：
链表的末尾节点 8 指向了链表中的节点 3，导致链表中出现了环形结构。
对于链表是否是由有环的判断方法有哪些呢？
3.1.1 穷举比较法
3.1.1.1 解题思想
(1)遍历链表，记录已访问的节点。
(2)将当前节点与之前以及访问过的节点比较，若有相同节点则有环。
否则，不存在环。
这种穷举比较思想简单，但是效率过于低下，尤其是当链表节点数目较多，在进行比较时花费大量时间，时间复杂度大致在 O(n^2)。这种方法自然不是出题人的理想答案。如果笔试面试中使用这种方法，估计就要跪了，忘了这种方法吧。
3.1.2 哈希缓存法
既然在穷举遍历时，元素比较过程花费大量时间，那么有什么办法可以提高比较速度呢？
3.1.2.1 解题思想
(1)首先创建一个以节点 ID 为键的 HashSe t集合，用来存储曾经遍历过的节点。
(2)从头节点开始，依次遍历单链表的每一个节点。
(3)每遍历到一个新节点，就用新节点和 HashSet 集合当中存储的节点作比较，如果发现 HashSet 当中存在相同节点 ID，则说明链表有环，如果 HashSet 当中不存在相同的节点 ID，就把这个新节点 ID 存入 HashSet ，之后进入下一节点，继续重复刚才的操作。
假设从链表头节点到入环点的距离是 a ，链表的环长是 r 。而每一次 HashSet 查找元素的时间复杂度是 O(1), 所以总体的时间复杂度是 1 * ( a + r ) = a + r，可以简单理解为 O(n) 。而算法的空间复杂度还是 a + r - 1，可以简单地理解成 O(n) 。
3.1.3 快慢指针法
3.1.3.1 解题思想
(1)定义两个指针分别为 slow，fast，并且将指针均指向链表头节点。
(2)规定，slow 指针每次前进 1 个节点，fast 指针每次前进两个节点。
(3)当 slow 与 fast 相等，且二者均不为空，则链表存在环。
3.1.3.2 图解过程
无环过程：
通过图解过程可以看出，若表中不存在环形，fast 与 slow 指针只能在链表末尾相遇。
有环过程：
图解过程可以看出，若链表中存在环，则快慢指针必然能在环中相遇。这就好比在环形跑道中进行龟兔赛跑。由于兔子速度大于乌龟速度，则必然会出现兔子与乌龟再次相遇情况。因此，当出现快慢指针相等时，且二者不为NULL，则表明链表存在环。
3.1.3.3 代码实现
bool isExistLoop(ListNode* pHead)  {  
    ListNode* fast;//慢指针，每次前进一个节点
    ListNode* slow;//快指针，每次前进2个节点 
    slow = fast = pHead ;  //两个指针均指向链表头节点
    //当没有到达链表结尾，则继续前进
    while (slow != NULL && fast -> next != NULL)  {  
        slow = slow -> next ; //慢指针前进一个节点
        fast = fast -> next -> next ; //快指针前进两个节点
        if (slow == fast)  //若两个指针相遇，且均不为NULL则存在环
            return true ;  
    }  
    //到达末尾仍然没有相遇，则不存在环
    return false ;  
}  
3.2 定位环入口
在 3.1 节中，已经实现了链表中是否有环的判断方法。那么，当链表中存在环，如何确定环的入口节点呢？
3.2.1 解题思想
slow 指针每次前进一个节点，故 slow 与 fast 相遇时，slow 还没有遍历完整个链表。设 slow 走过节点数为 s，fast 走过节点数为 2s。设环入口点距离头节点为 a，slow 与 fast 首次相遇点距离入口点为 b，环的长度为 r。
则有：
s = a + b;
2s = n * r + a + b; n 代表fast指针已经在环中循环的圈数。
则推出：
s = n * r; 意味着slow指针走过的长度为环的长度整数倍。
若链表头节点到环的末尾节点度为 L，slow 与 fast 的相遇节点距离环入口节点为 X。
则有：
a+X = s = n * r = (n - 1) * r + (L - a);
a = (n - 1) * r + (L - a - X);
上述等式可以看出：
从 slow 与 fast 相遇点出发一个指针 p1，请进 (L - a - X) 步，则此指针到达入口节点。同时指针 p2 从头结点出发，前进 a 步。当 p1 与 p2 相遇时，此时 p1 与 p2 均指向入口节点。
例如图3.1所示链表：
slow 走过节点 s = 6；
fast 走过节点 2s = 12；
环入口节点据流头节点 a = 3；
相遇点距离头节点 X = 3；
L = 8；
r = 6；
可以得出 a = (n - 1) * r + (L - a - X)结果成立。
3.2.2 图解过程
3.2.3 代码实现
//找到环中的相遇节点
ListNode* getMeetingNode(ListNode* pHead) // 假设为带头节点的单链表{
    ListNode* fast;//慢指针，每次前进一个节点
    ListNode* slow;//快指针，每次前进2个节点 
    slow = fast = pHead ;  //两个指针均指向链表头节点
    //当没有到达链表结尾，则继续前进
    while (slow != NULL && fast -> next != NULL){  
        slow = slow -> next ; //慢指针前进一个节点
        fast = fast -> next -> next ; //快指针前进两个节点
        if (slow == fast)  //若两个指针相遇，且均不为NULL则存在环
            return slow;  
    }  

    //到达末尾仍然没有相遇，则不存在环
    return NULL ;
}
//找出环的入口节点
ListNode* getEntryNodeOfLoop(ListNode* pHead){
    ListNode* meetingNode = getMeetingNode(pHead); // 先找出环中的相遇节点
    if (meetingNode == NULL)
        return NULL;
    ListNode* p1 = meetingNode;
    ListNode* p2 = pHead;
    while (p1 != p2) // p1和p2以相同的速度向前移动，当p2指向环的入口节点时，p1已经围绕着环走了n圈又回到了入口节点。
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    //返回入口节点
    return p1;
}
3.3 计算环长度
3.3.1 解题思想
在3.1中找到了 slow 与 fast 的相遇节点，令 solw 与 fast 指针从相遇节点出发，按照之前的前进规则，当 slow 与fast 再次相遇时，slow 走过的长度正好为环的长度。
3.3.2 图解过程
3.3.3 代码实现
int getLoopLength(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while ( fast && fast->next ){
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast )//第一次相遇
            break;
    }
    //slow与fast继续前进
    slow = slow->next;
    fast = fast->next->next;
    int length = 1;       //环长度
    while ( fast != slow )//再次相遇
    {
        slow = slow->next;
        fast = fast->next->next;
        length ++;        //累加
    }
    //当slow与fast再次相遇，得到环长度
    return length;
}
4 使用链表实现大数加法 
4.1 问题描述
两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
例如：
输入：
3->1->5->null 
5->9->2->null，
输出：
8->0->8->null
4.2 代码实现
ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
        ListNode *ret = l1, *pre = l1;
        int up = 0;
        while (l1 != NULL && l2 != NULL) {
            //数值相加
            l1->val = l1->val + l2->val + up;
            //计算是否有进位
            up = l1->val / 10;
            //保留计算结果的个位
            l1->val %= 10;
            //记录当前节点位置
            pre = l1;
            //同时向后移位
            l1 = l1->next;
            l2 = l2->next;
        }
        //若l1到达末尾，说明l1长度小于l2
        if (l1 == NULL)
            //pre->next指向l2的当前位置
            pre->next = l2;
        //l1指针指向l2节点当前位置
        l1 = pre->next;
        //继续计算剩余节点
        while (l1 != NULL) {
            l1->val = l1->val + up;
            up = l1->val / 10;
            l1->val %= 10;
            pre = l1;
            l1 = l1->next;
        }

        //最高位计算有进位，则新建一个节点保留最高位
        if (up != 0) {
            ListNode *tmp = new ListNode(up);
            pre->next = tmp;
        }
        //返回计算结果链表
        return ret;
}
5 有序链表合并 
5.1 问题描述
题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：
1->2->4, 
1->3->4 
输出：
1->1->2->3->4->4
5.2 一般方案
5.2.1 解题思想
(1)对空链表存在的情况进行处理，假如 pHead1 为空则返回 pHead2 ，pHead2 为空则返回 pHead1。(两个都为空此情况在pHead1为空已经被拦截)
(2)在两个链表无空链表的情况下确定第一个结点，比较链表1和链表2的第一个结点的值，将值小的结点保存下来为合并后的第一个结点。并且把第一个结点为最小的链表向后移动一个元素。
(3)继续在剩下的元素中选择小的值，连接到第一个结点后面，并不断next将值小的结点连接到第一个结点后面，直到某一个链表为空。
(4)当两个链表长度不一致时，也就是比较完成后其中一个链表为空，此时需要把另外一个链表剩下的元素都连接到第一个结点的后面。
5.2.2 代码实现
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* pTail = NULL;//指向新链表的最后一个结点 pTail->next去连接
    ListNode* newHead = NULL;//指向合并后链表第一个结点
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL == pHead2){
        return pHead1;
    }else{
        //确定头指针
        if ( pHead1->data data){
            newHead = pHead1;
            pHead1 = pHead1->next;//指向链表的第二个结点
        }else{
            newHead = pHead2;
            pHead2 = pHead2->next;
        }
        pTail = newHead;//指向第一个结点
        while ( pHead1 && pHead2) {
            if ( pHead1->data <= pHead2->data ){
                pTail->next = pHead1;  
                pHead1 = pHead1->next;
            }else {
                pTail->next = pHead2;
                pHead2 = pHead2->next;
            }
            pTail = pTail->next;

        }
        if(NULL == pHead1){
            pTail->next = pHead2;
        }else if(NULL == pHead2){
            pTail->next = pHead1;
        }
        return newHead;
}
5.3 递归方案
5.3.1 解题思想
(1)对空链表存在的情况进行处理，假如 pHead1 为空则返回 pHead2 ，pHead2 为空则返回 pHead1。
(2)比较两个链表第一个结点的大小，确定头结点的位置
(3)头结点确定后，继续在剩下的结点中选出下一个结点去链接到第二步选出的结点后面，然后在继续重复(2 )(3) 步，直到有链表为空。
5.3.2 代码实现
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* newHead = NULL;
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL ==pHead2){
        return pHead2;
    }else{
        if (pHead1->data data){
            newHead = pHead1;
            newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
        }else{
            newHead = pHead2;
            newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
         }
        return newHead;
    }   
}
6 删除链表中节点，要求时间复杂度为O(1) 
6.1 问题描述
给定一个单链表中的表头和一个等待被删除的节点。请在 O(1) 时间复杂度删除该链表节点。并在删除该节点后，返回表头。
示例：
给定 1->2->3->4，和节点 3，返回 1->2->4。
6.2 解题思想
在之前介绍的单链表删除节点中，最普通的方法就是遍历链表，复杂度为O(n)。 
如果我们把删除节点的下一个结点的值赋值给要删除的结点，然后删除这个结点，这相当于删除了需要删除的那个结点。因为我们很容易获取到删除节点的下一个节点，所以复杂度只需要O(1)。
示例 
单链表：1->2->3->4->NULL 
若要删除节点 3 。第一步将节点3的下一个节点的值4赋值给当前节点。变成 1->2->4->4->NULL，然后将就 4 这个结点删除，就达到目的了。 1->2->4->NULL
如果删除的节点的是头节点，把头结点指向 NULL。 
如果删除的节点的是尾节点，那只能从头遍历到头节点的上一个结点。
6.3 图解过程
6.4 代码实现
void deleteNode(ListNode **pHead, ListNode* pDelNode) {
        if(pDelNode == NULL)
            return;
        if(pDelNode->next != NULL){
            ListNode *pNext = pDelNode->next;
            //下一个节点值赋给待删除节点
            pDelNode->val   =  pNext->val;
            //待删除节点指针指后面第二个节点
            pDelNode->next  = pNext->next;
            //删除待删除节点的下一个节点
            delete pNext;
            pNext = NULL;
        }else if(*pHead == pDelNode)//删除的节点是头节点
         {
            delete pDelNode;
            pDelNode= NULL;
            *pHead = NULL;
        } else//删除的是尾节点
        {
            ListNode *pNode = *pHead;
            while(pNode->next != pDelNode) {
                pNode = pNode->next;
            }
            pNode->next = NULL;
            delete pDelNode;
            pDelNode= NULL;
        }
    }
7 从尾到头打印链表 
7.1 问题描述
输入一个链表，按链表值从尾到头的顺序返回一个 ArrayList 。
7.2 解法
初看题目意思就是输出的时候链表尾部的元素放在前面，链表头部的元素放在后面。这不就是 先进后出，后进先出 么。
什么数据结构符合这个要求？
栈 ！
7.2.1 代码实现
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        ListNode *p=NULL;
        p=head;
        stack<int> stk;
        while(p!=NULL){
            stk.push(p->val);
            p=p->next;
        }
        while(!stk.empty()){
            value.push_back(stk.top());
            stk.pop();
        }
        return value;
    }
};
7.3 解法二
第二种方法也比较容易想到，通过链表的构造，如果将末尾的节点存储之后，剩余的链表处理方式还是不变，所以可以使用递归的形式进行处理。
7.3.1 代码实现
class Solution {
public:
    vector<int> value;
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p=NULL;
        p=head;
        if(p!=NULL){
            if(p->next!=NULL){
                printListFromTailToHead(p->next);
            }
            value.push_back(p->val);
        }
        return value;
    }
};
8 反转链表 
8.1 题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
8.2 解题思路
设置三个节点pre、cur、next
(1)每次查看cur节点是否为NULL，如果是，则结束循环，获得结果
(2)如果cur节点不是为NULL，则先设置临时变量next为cur的下一个节点
(3)让cur的下一个节点变成指向pre，而后pre移动cur，cur移动到next
(4)重复(1)(2)(3)
8.3 动画演示
8.4 代码实现
8.4.1 迭代方式
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};
8.4.2 递归的方式处理
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归终止条件
        if(head == NULL || head->next == NULL)
            return head;

        ListNode* rhead = reverseList(head->next);
        // head->next此刻指向head后面的链表的尾节点
        // head->next->next = head把head节点放在了尾部
        head->next->next = head;
        head->next = NULL;
        return rhead;
    }
};
End
本文由小吴和他的小伙伴 进击的Hello_World 共同整理完成~
今日问题：
通过本文的学习，以后遇到有关链表的面试问题我们有哪些思路去解决？
打卡格式：
打卡 X 天，答：xxx 。
欢迎关注这个会做动画的程序员?
如果文章有帮助，点个“好看”吧！