5. 链表

1. 876. 链表的中间结点

/**
 * 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
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *tmp=head;
        int length=0;        
        // 选遍历一遍拿到链表长度
        while(tmp!=NULL){
            length++;
            tmp=tmp->next;
        }
        tmp=head;
        int k=0;
        // 再遍历一遍拿到链表中间结点
        while(k<length/2){
            k++;
            tmp=tmp->next;
        }
        return tmp;
    }
};
//解法2：快慢指针
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast!=NULL&&fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

2. 19. 删除链表的倒数第 N 个结点 与 剑指 Offer II 021. 删除链表的倒数第 n 个结点

//快慢指针
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow=head;
        ListNode *fast=head;
        //先找到k个节点的区间
        while(n>0){
            fast=fast->next;
            n--;
        }
        //说明删除的是头结点
        if(fast==NULL){
            return head->next;
        }
        //区间平行移动，删除slow节点即可
        while(fast->next!=NULL){
            slow=slow->next;
            fast=fast->next;
        }
        slow->next=slow->next->next;
        return head;
    }
};

3. 剑指 Offer 22. 链表中倒数第k个节点

//快慢指针
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(k>0){
            fast=fast->next;
            k--;
        }
        if(fast==NULL){
            return head;
        }
        while(fast->next!=NULL){
            slow=slow->next;
            fast=fast->next;
        }
        return slow->next;
    }
};

4. 61. 旋转链表

class Solution {
public:    
    ListNode* slow;
    ListNode* fast;
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        //压缩k
        int length=0;
        ListNode* tmp=head;
        while(tmp){
            tmp=tmp->next;
            length++;
        }
        k=k%length;
        ListNode* K1Node=findKthToTail(head,k);
        if(fast==NULL){
            return NULL;
        }
        //末尾的next为前半部分
        fast->next=head;
        //第二段变为第一段
        head=K1Node->next;
        //第一段next变null
        K1Node->next=NULL;
        return head;
    }
    //双指针平行移动找到
    ListNode* findKthToTail(ListNode* head,int k){
        slow=fast=head;
         //先找到倒数第k+1个
        while(k>0){
            if(fast->next==NULL){
                fast=head;
            }else{ 
                fast=fast->next;
            }
            k--;
        }
        if(fast==NULL){
            return head;
        }
        while(fast->next!=NULL){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

5. 2095. 删除链表的中间节点

//双指针
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return NULL;
        }
        ListNode *slow=head,*fast=head,*pre=NULL;
        while(fast!=NULL&&fast->next!=NULL){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        pre->next=slow->next;
        return head;
    }
};

6. 剑指 Offer II 023. 两个链表的第一个重合节点 与 160. 相交链表

//重合之后都相同，让长的先走一段距离（长度之差），然后一起走，节点重合返回
class Solution {
public:
    int getLength(ListNode *head){
        int n=0;
        while(head){
            head=head->next;
            n++;
        }
        return n;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len1=getLength(headA),len2=getLength(headB);
        int n=len1-len2;
        ListNode *longer=n>0?headA:headB;
        ListNode *shorter=n>0?headB:headA;
        n=(n>0)?n:(-n);
        for(int i=0;i<n;i++){
            longer=longer->next;
        }
        while(longer!=shorter){
            longer=longer->next;
            shorter=shorter->next;
        }
        return longer;
    }
};

7. 141. 环形链表

//快慢指针相遇时有环
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow=head,*fast=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;

            if(fast==NULL){
                return false;
            }
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
};

8. 142. 环形链表 II 与 剑指 Offer II 022. 链表中环的入口节点

class Solution {
public:
    ListNode *detectCycle(ListNode *head){
        ListNode *fast=head,*slow=head;
        while(fast){
            slow=slow->next;
            if(fast->next==NULL){
                return NULL;
            }
            fast=fast->next->next;
            //相遇时，从相遇点和head再次出发，再次相遇就是入口，数学推算
            if(slow==fast){
                ListNode *tmp=head;
                while(tmp!=slow){
                    tmp=tmp->next;
                    slow=slow->next;
                }
                return tmp;
            }
        }
        return NULL;
    }
};

9. 206. 反转链表 与 剑指 Offer 24. 反转链表 与 剑指 Offer II 024. 反转链表

class Solution {
public:
//递归
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* tmp=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return tmp;
    }
};

//非递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=NULL,*cur=head,*tmp=NULL;
        while(cur!=NULL){
            //改变指针指向
            tmp=cur->next;
            cur->next=pre;
            //改变pre cur
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

10. 92. 反转链表 II

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==right){
            return head;
        }
        ListNode *tmp=head;
        ListNode *beginPre=NULL,*begin=NULL,*pre=NULL,*cur=NULL;
        for(int i=1;i<left;i++){
            if(i==left-1){
                beginPre=tmp;
            }
            tmp=tmp->next;
        }
        pre=beginPre;
        cur=tmp;
        begin=tmp;
        for(int i=left;i<=right;i++){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        } 

        //边界问题
        if(beginPre){
            beginPre->next=pre; 
        }else{
            head=pre;
        }
        if(begin){
            begin->next=cur;
        }else{
            head->next=cur;
        }
        return head;           
    }
};

11. 25. K 个一组翻转链表

class Solution {
public:
    //数k个，代入reverse反转。注意头尾
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL){
            return NULL;
        }
        ListNode *start=head,*end=head;
        for(int i=0;i<k;i++){
            if(end==NULL) return head;
            end=end->next;
        }
        ListNode *newHead=reverse(start,end);
        start->next=reverseKGroup(end,k);
        return newHead;
    }
    //K个一组进行反转，双指针
    ListNode* reverse(ListNode* head,ListNode* tail){
        ListNode* pre=NULL,*cur=head;
        while(cur!=tail){
            ListNode* tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

12. 203. 移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //判断头结点
        while(head!=NULL&&head->val==val){
            head=head->next;
        }        
        ListNode *cur=head;
        //非头结点
        while(cur&&cur->next){
            //相等则
            if(cur->next->val==val){
                cur->next=cur->next->next;
            }else{  //不相等继续往后
                cur=cur->next;
            }
        }
        return head;
    }
};

13. 707. 设计链表

//虚拟头结点
class MyLinkedList {
public:
    struct LinkedNode{
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val),next(NULL){}
    };
    MyLinkedList() {
        _dummyHead=new LinkedNode(0);
        _size=0;
    }

    int get(int index) {
        if(index>(_size-1)||index<0){
            return -1;
        }
        LinkedNode* cur=_dummyHead->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val) {
        LinkedNode* newNode=new LinkedNode(val);
        newNode->next=_dummyHead->next;
        _dummyHead->next=newNode;
        _size++;
    }

    void addAtTail(int val) {
        LinkedNode* newNode=new LinkedNode(val);
        LinkedNode* cur=_dummyHead;
        while(cur->next){
            cur=cur->next;
        }
        cur->next=newNode;
        _size++;
    }

    void addAtIndex(int index, int val) {
        if(index>_size){
            return;
        }
        LinkedNode* cur=_dummyHead;
        LinkedNode* newNode=new LinkedNode(val);
        while(index--){
            cur=cur->next;
        }
        newNode->next=cur->next;
        cur->next=newNode;
        _size++;
    }

    void deleteAtIndex(int index) {
        if(index<0||index>=_size){
            return;
        }
        LinkedNode* cur=_dummyHead;
        while(index--){
            cur=cur->next;
        }
        cur->next=cur->next->next;
        _size--;
    }

private:
    LinkedNode* _dummyHead;
    int _size;
};

14. 21. 合并两个有序链表

/**
 * 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&&p2){
            if(p1->val>p2->val){
                p->next=p2;
                p2=p2->next;
                p=p->next;
            }else{
                p->next=p1;
                p1=p1->next;
                p=p->next;
            }
        }
        if(p1){
            p->next=p1;
        }
        if(p2){
            p->next=p2;
        }
        return dummy->next;
    }
};