3道中等+2道简单
数组和字符串打算告一段落，正好最近做的几乎都是双指针，所以今天做链表！

1、合并两个有序链表（难度：简单）

该题对应力扣网址

AC代码

思路简单

/**
 * 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* dummy = new ListNode(-1), *p=dummy;
        ListNode* p1=list1, *p2=list2;

        while(p1!=NULL && p2!=NULL){
            if(p1->val<p2->val){
                p->next=p1;
                p1=p1->next;
            }
            else{
                p->next=p2;
                p2=p2->next;
            }
            p=p->next;
        }
        if(p1!=NULL){
            p->next=p1;
        }
        if(p2!=NULL){
            p->next=p2;
        }
        return dummy->next;
    }
};

2、分隔链表（难度：中等）

该题对应力扣网址

AC代码

思路比较简单，就是把一个链表先拆分成两个链表，再拼接。

/**
 * 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* partition(ListNode* head, int x) {
        ListNode* head1=new ListNode(-1);
        ListNode* head2=new ListNode(-1);
        ListNode* p=head;
        ListNode* p1=head1, *p2=head2;
        ListNode* s;
        while(p!=NULL){
            if(p->val<x){
                s=new ListNode(p->val);
                p1->next=s;
                p1=s;
            }
            else{
                s=new ListNode(p->val);
                p2->next=s;
                p2=s;
            }
            p=p->next;
        }
        p1->next=head2->next;

        return head1->next;
    }
};

3、删除链表的倒数第N个结点（难度：中等）

该题对应力扣网址

AC代码

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        ListNode* p=dummy;
        n=n+1;
        while(n--){
            p=p->next;
        }
        ListNode* p1=dummy;
        ListNode* p2=p;
        while(p2!=NULL){
            p2=p2->next;
            p1=p1->next;
        }
        p1->next=p1->next->next;
        return dummy->next;
    }
};

4、链表的中间结点（难度：简单）

该题对应力扣网址

AC代码

使用快慢指针，fast比low指针每次都多走一步。
需要注意的是，空指针的情况，在循环条件里要明确。

/**
 * 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* middleNode(ListNode* head) {
        ListNode* low=head, *fast=head;
        while(fast!=NULL && fast->next!=NULL){
            low=low->next;
            fast=fast->next->next;
        }
        return low;
    }
};

5、合并两个链表（难度：中等）

该题力扣对应网址

AC代码

模拟，寻常思路，不说了，有点水

/**
 * 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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode* pre=list1;
        for(int i=0;i<a-1;i++){
            pre=pre->next;
        }
        ListNode* pre1=pre;
        for(int j=a;j<=b;j++){
            pre1=pre1->next;
        }
        ListNode* rear=list2;
        while(rear->next!=NULL){
            rear=rear->next;
        }
        pre->next=list2;
        rear->next=pre1->next;
        return list1;
    }
};