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