什么是链表？直观地通过代码解析如下（注意链表在cpp中不是一个预定义的数据类型，为此需要自己定义～）：


 //Definition for singly-linked list.
 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

1. 合并两个有序链表

原本我的解法是用递归去做的，对应的复杂度是O(n+m)


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void calulate(ListNode* list1, ListNode* list2,ListNode* &result_list)//注意输入的用指针的引用
     {
        if(list1==nullptr && list2==nullptr)
        {
            result_list=nullptr;//置空
            return;//直到两个都为空的时候，就返回
        }
        else if(list1!=nullptr && list2!=nullptr)//两个都不为空
        {
            if(list1->val<=list2->val)
            {
                result_list->val=list1->val;
                list1=list1->next;//迭代到下一个指针
            }
            else
            {
                result_list->val=list2->val;
                list2=list2->next;
            }
            result_list->next = new ListNode();// 初始化 result_list->next 以防止空指针访问
            calulate(list1, list2, result_list->next);
        }
        else if(list1==nullptr || list2==nullptr)//若两者有一个为空
        {
            ListNode *no_empty= (list1==nullptr? list2: list1);//非空的一个
            result_list=no_empty;//直接等于非空的一个~
            return;//返回
        }
     }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 采用递归的方法去解决
       ListNode* result_list=new ListNode(0);//初始化为0，为一个指针，指针的初始化为new
       calulate(list1, list2,result_list);
       return result_list; 
    }
};

此处改为采用双指针去解。时间复杂度应该是一样的，但是空间复杂度不一样。上面的递归的空间复杂度为O(n+m)。递归调用函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。而用双指针来解题，空间复杂度为O(1)。因为只需要常数的空间来存放若干变量。
理解过程如下动图所示：


  /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode() : val(0), next(nullptr) {}
  *     ListNode(int x) : val(x), next(nullptr) {}
  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  * };
  */
 class Solution {
 public:
     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
         // 创建一个空的链表作为输出（此处采用的是虚拟头节点）
         ListNode* result=new ListNode(0);//第一个是占位符，头节点不要，返回的为result->next
         ListNode* p=result;//创建指向这个链表的指针
 
         // 创建分别指向两个链表的指针
         ListNode* p1=list1;
         ListNode* p2=list2;
 
         while(p1!=nullptr && p2!=nullptr)
         {
             if(p1->val < p2->val)//若p1当前的值小于p2,赋值p1
             {
                 p->next=p1;//永远都是放到next中，这样就可以避免下一次访问空指针
                 p1=p1->next;//p1继续递推
             }
             else//若p1当前的值大于p2，赋值p2
             {
                  p->next=p2;
                 p2=p2->next;//p2继续递推
             }
             p=p->next;//p也继续递推
         }
 
         if(p1!=nullptr)//若1还没结束，接到末尾
         {
             p->next=p1;
         }
 
         if(p2!=nullptr)//若2还没结束。接到末尾
         {
             p->next=p2;
         }
 
         return result->next;//注意返回的为除第一个以外的
     }
 };

注意上面解法返回的是result->next。采用的是「虚拟头结点」。
另外一种解法可以直接返回result，但是不采用虚拟头节点的话就要额外处理指针 p 为空的情况：

  
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode() : val(0), next(nullptr) {}
    *     ListNode(int x) : val(x), next(nullptr) {}
    *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    * };
    */
   class Solution {
   public:
       ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
           if(list1==nullptr && list2==nullptr)
               return list1;
           // 创建一个空的链表作为输出
           ListNode* result=new ListNode(0);
           ListNode* p=result;//创建指向这个链表的指针
   
           // 创建分别指向两个链表的指针
           ListNode* p1=list1;
           ListNode* p2=list2;
   
           while(p1!=nullptr && p2!=nullptr)
           {
               if(p1->val < p2->val)//若p1当前的值小于p2,赋值p1
               {
                   p->val=p1->val;
                   p1=p1->next;//p1继续递推
               }
               else//若p1当前的值大于p2，赋值p2
               {
                   p->val=p2->val;
                   p2=p2->next;//p2继续递推
               }
               p->next=new ListNode();// 初始化  以防止空指针访问
               p=p->next;//p也继续递推
   
           }
   
           if(p1!=nullptr || p2!=nullptr)//若有没空的，接到末尾
           {
               ListNode *no_empty= (p1==nullptr? p2: p1);//非空的一个
               p->val=no_empty->val;
               p->next=no_empty->next;
           }
   
           return result;
       }
   };

2. 分隔链表

看到这道题的时候，第一个解决思路如下。将原链表一分为2，然后把大的链表放在小的链表后。通过两个链表，一个用来存放小于阈值的，另外一个用来存放大于阈值的。最后再把两个链表合并起来。
注意需要 p_bigger->next = nullptr; 来处理尾节点，避免循环引用。由于当前节点p_bigger复用的是原链表head的节点，而其 next 指针可能指向一个小于 x 的节点，需要切断这个引用。
时间复杂度为O（n），空间复杂度为O（1）

下面解法则是直接在循环的时候就断开原链表的每个节点的next指针。
原因是采用的是链表赋值，那么原来的链表的next指针可能就继续指向其他节点，这样就很容易形成类似环路的结构。所以在赋值的时候，需要把原链表的每个节点的next指针断开，置为空。（PS：若通过val关键字赋值，而不是用next指针赋值，那也可以解决）
总的来说，如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了。

下面就是上面提到的，通过new ListNode来给指针赋值，那么就不需要每次额外断掉

3. 合并 k 个有序链表

第一眼最基本的解法就是遍历(递归)用两两合并的方式。对于vector长度为k，每个链表最长的长度为n。第一次合并后，长度为n，第二次合并后为2n。第三次为3n，依次类推O（（1+k）k/2*n）那么就是O（k²*n）。空间复杂度为O（1）.

更优的解法则是采用优先队列的思路，从k个链表的头节点的指针中来找最小的放入。
优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)。
所有的链表节点都会被加入和弹出 pq，所以算法整体时间复杂度是O(n*logk)。空间复杂度则由于用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)

下面是优先级队列的解法(关于优先队列请见参考资料，可以理解为本身在优先级队列中进行了排序了只是把结果存出来而已～):

采用lambda表达式的做法：

4. 单链表的倒数第 k 个节点

对于这类型的题目，最直接的方式当然就是先遍历一次得到链表的长度为n，然后再遍历一次得到倒数第k个节点（也就是正数的第n-k+1个节点）。但这样做的话需要两次遍历，能否只遍历一次呢？
思路请见下图：

解题的代码如下，时间复杂度为O（N），空间复杂度为O（N）如果不额外用一个虚拟节点的话，空间复杂度为O（1）。

双指针法提取链表倒数第k个值。此题跟上一题其实是一样的，关键其实是输入数据构建成链表

4. 快慢指针获取单链表的中点

同样是双指针法，慢指针走一步，快指针走两步，这样当快指针走到终点时，慢指针就是中间点。

代码如下：

5. 快慢指针获取判断链表是否包含环

如果 fast 最终能正常走到链表末尾，说明链表中没有环；如果 fast 走着走着竟然和 slow 相遇了，那肯定是 fast 在链表中转圈了，说明链表中含有环。

时间复杂度为O（N）与空间为O（1）

也可以采用hash table的形式来查看当前的节点是否已经访问过，如果访问过则说明有环，时间复杂度为O（N），空间复杂度为O（N）

进阶版：如果链表中含有环，如何计算这个环的起点？

此题用哈希表解更加简单，空间复杂度与时间复杂度都是O(N)

若要采用快慢指针，思路相对比较绕，请见图例。
注意跟哈希表不一样，快慢指针只是找到环的相遇点，而不是环的起点。快慢指针是通过判断是否有相遇点确定是否为环。而哈希表则是直接找到环的起点。

6. 两个链表是否相交

最直接的解题思路应该是使用哈希集合存储链表节点，然后遍历另一个链表，看是否有相同的节点。时间复杂度为O（m+n），空间复杂度为O（m）或O（n）。

此处只看双指针法。解题思路见下图。时间复杂度为时间复杂度：O(m+n)，空间复杂度为O（1）

7. 删除排序链表中的重复元素

由于是已经排序的链表，最直接的思路应该是两两对比，如果遇到相同的就跳过去

也可以采用快慢针法，具体见下动图解析以及代码：

8. 其他链表类题目

除了上述的采用双指针法解决的链表类题目外，大部分的链表类题目其实都可以用递归来解决的。接下来逐一介绍
关于递归类题目的介绍，请见博客Link

两数相加

反转链表：全部

解决方法等效于在链表的头部插入一个节点，时间复杂度为O（N）：

解法2:虽然写了很多指针，但是思路很清晰

下面更好理解～

反转链表：范围内

关键点在于右指针如何让递归回到改回到的点：


  
  class Solution {
    public:
    
        void calculate(ListNode* head, const int left, const int right,ListNode* &result, int index)
        {
            if(head==nullptr)//到达了终点（head为空）
                return;//为空则返回
            
            if(index<left)//此时还不需要反转，顺序即可
            {
                ListNode* newlistnode=new ListNode(head->val);//用当前值创建链表。
                result=newlistnode;//result为当前的值
                calculate(head->next,left,right,result->next,index+1);//计算各自的下一个指针
            }       
            else if(index>=left && index<=right)//需要倒序
            {
                ListNode* newlistnode=new ListNode(head->val);//当前的值
                newlistnode->next=result;//当前的result作为next
                result=newlistnode;//获取当前的值（此处类似在节点头插入一个节点）
                calculate(head->next,left,right,result,index+1);
            }
            else if(index>right)//要恢复回顺序
            {
                // *关键：此时result的指针还是位于left上;要让它回到right上
                // if(index<=right+(right-left+1))
                //     calculate(head,left,right,result->next,index+1);//指针递增
                // else//回到right上了
                // {
                //     result=head;//最后全部赋值
                //     return;
                // }
    
                // 让result的指针前进到right
                int temp_int=right-left;
                ListNode* p_result=result;
                while(temp_int)
                {
                    p_result=p_result->next;
                    temp_int--;
                }
                p_result->next=head;//将最后的全部直接赋值
                return;
            }
        }
    
        ListNode* reverseBetween(ListNode* head, int left, int right) {
    
            ListNode* result=nullptr;//创建空的链表
            int index=1;//从1开始
            //用迭代的解法
            calculate(head,left,right,result,index);
            return result;
        }
    };