算法—链表操作

        掌握数据结构链表的头插和尾插，删除，查找的操作，然后就可以根据题目要求实现其操作组合。

        对于链表来说，画图更好理解题解中的具体步骤，否则难以理解代码实际对数据结构的操作。

2. 两数相加 - 力扣（LeetCode）

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* new_list=new ListNode(0);
        ListNode* back=new_list;
        ListNode* cur1=l1;  ListNode* cur2=l2;
        int t=0;
        while(cur1||cur2||t){
            if(cur1){
               t+=cur1->val; 
               cur1=cur1->next;
            }
            if(cur2){
                t+=cur2->val;
               cur2=cur2->next;
            }
 
            int tmp=t%10;
            back->next=new ListNode(tmp);
            back=back->next;
            t=t/10;
        }
        
        ListNode* ret=new_list->next;
        delete new_list;
        return ret;
    }
};

24. 两两交换链表中的节点 - 力扣（LeetCode）

/**
 * 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* swapPairs(ListNode* head) {
        if(!(head&&head->next)) return head;
        ListNode* new_list=new ListNode(0);
        new_list->next=head;
 
        ListNode* prev=new_list;
        ListNode* cur= head;
        ListNode* cur_n= head->next;
 
        ListNode* cur_n_n=cur_n->next;//记录将要移动到下次的位置
        while(cur&&cur_n){
            cur_n_n=cur_n->next;
            prev->next=cur_n;
            cur->next=cur_n_n;
            cur_n->next=cur;
            cout<<"cur:"<<cur->val<<"cur_n:"<<cur_n->val<<endl;;
            //下个位置
            prev=cur;//**1***cur位置移动到后面了
            cur=prev->next;
            if(cur)
            cur_n=cur->next;
        }   
        
        ListNode* ret=new_list->next;
        delete new_list;
        return ret;
        
 
    }
};

143. 重排链表 - 力扣（LeetCode）

/**
 * 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://算法原理：将题目分解为两个0~n/2和n/2~n的链表，然后让后面的链表反转，依次交替插入。
    void reorderList(ListNode* head) {
        //从中间分解链表：左右指针
        ListNode* slow=head; ListNode* fast=head;
        while(fast->next&&fast->next->next){//fast->next=nullptr为结点数为偶数的链表，next->next为奇数
            slow=slow->next;
            fast=fast->next->next;
        }
        //分析后slow为0~n/2的链表的末结点
        ListNode* new_list=new ListNode;
        //反转0~n/2的链表
        ListNode *cur=slow->next;
        slow->next=nullptr;
        while(cur){
            ListNode* cur_n=cur->next;
            cur->next=new_list->next;
            new_list->next=cur;
            cur=cur_n;
        }
        
        //两链表交错链接，因为前面的操作0~n/2可能多一个点，所以cur2插入cur1后
        ListNode* cur1=head ; ListNode* cur2=new_list->next;
        while(cur1&&cur2){
            ListNode* cur1_n=cur1->next;
            ListNode* cur2_n=cur2->next;
            cur2->next=cur1->next;//cur2插入cur1后
            cur1->next=cur2;
            cur1=cur1_n;
            cur2=cur2_n;
        }
        return ;//不用返回
    }
};

23. 合并 K 个升序链表 - 力扣（LeetCode）

/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        //归并排序->对于有效链表
        int n=lists.size();
        return mergesort(lists,0,n-1);//**1** n-1记得
    }
 
    ListNode* mergesort(vector<ListNode*>& lists,int left,int right){
        if(left==right) return lists[left];
        if(left>right) return nullptr;
        int mid=(left+right)/2;
        ListNode* list1=mergesort(lists,left,mid);
        ListNode* list2=mergesort(lists,mid+1,right);
        
        return merge_2List(list1,list2);
    }
 
    ListNode* merge_2List(ListNode* list1,ListNode* list2){
        ListNode * new_list = new ListNode;
        ListNode * back=new_list;
        
        ListNode *cur1=list1;
        ListNode *cur2=list2;
        while(cur1&&cur2){
            if(cur1->val <= cur2->val){
                back=back->next=cur1;
                cur1=cur1->next;
            }else{
                back=back->next=cur2;
                cur2=cur2->next;
            }
        }
        while(cur1){
            back=back->next=cur1;
            cur1=cur1->next;
        }
        while(cur2){
            back=back->next=cur2;
            cur2=cur2->next;
        }
        back= new_list->next;
        delete new_list;
        return back;
    }
};

 25. K 个一组翻转链表 - 力扣（LeetCode）

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        int n=0;
        ListNode *i=head;
        while(i){
            i=i->next;
            n++;
        }
        int len=n/k;//需要头插几次反转
        ListNode *new_list= new ListNode;
 
        ListNode* tmp=new_list;
        ListNode* cur=head;
        ListNode *next=nullptr;
        while(len--){
            ListNode* prev = tmp;
            tmp=cur;
            for(int i=0;i<k;i++){
                next=cur->next;
                cur->next=prev->next;
                prev->next=cur;
                cur=next;
            }
        }
        //链接末尾小于k不反转的结点
        tmp->next=next;//或者=cur，因为cur已经指向下一个结点
        tmp=new_list->next;
        delete new_list;
        return tmp;
    }
};