leetcode25,k个一组翻转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

class Solution {
public:
    // reverse from node a to node b
    ListNode* Reverse(ListNode* a, ListNode* b){
        ListNode* pre = nullptr;
        ListNode* cur = a;
        while(pre != b) {
            auto nxt = cur->next;
            cur->next = pre;
            pre = cur; cur = nxt;
        }
        return pre;
    }// a->...->b  to  b->...->a->nullptr

    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head || k == 0 || k == 1) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        int sum = 0;
        auto tmp = head;
        while(tmp) {
            sum++;
            tmp = tmp->next;
        }
        ListNode* pre = dummy;
        ListNode* right = head;

        for(int i = 0; i < sum; i += k) {
            ListNode* left = pre->next;
            for(int j = i; j < i+k-1; j++) { // j-i+1 == k               
                right = right->next;  
                if(right == nullptr) return dummy->next;     
            }
            ListNode* tail = right->next; // 后半截

            Reverse(left, right);// return right,也可写成return void
            pre->next = right; // pre->接上
            left->next = tail;

            pre = left; //记录更新 pre=
            right = pre->next;
        }

        return dummy->next;
        ///////如果递归写法更简洁
    }
};

class Solution {
public:
    // reverse from node a to node b, not include b
    ListNode* Reverse(ListNode* a, ListNode* b){
        ListNode* pre = nullptr;
        ListNode* cur = a;
        while(cur != b) {
            auto nxt = cur->next;
            cur->next = pre;
            pre = cur; cur = nxt;
        }
        return pre;
    }// a->...->b  to  nullptr<-a<-... x b->... return x

    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head || k == 0 || k == 1) return head;
        ///////递归写法
        ListNode* left = head;
        ListNode* right = head;
        for(int i = 0; i < k; i++) {
            if(right == nullptr) return head;
            right = right->next;// k=2, 0.1.2.下一个right==2

        }
        ListNode* tail = Reverse(left, right);
        left->next = reverseKGroup(right, k); //1->后面

        return tail;
    }
};

leetcode92,区间内翻转链表

https://leetcode-cn.com/problems/reverse-linked-list-ii/

class Solution {
public:
    void reverse(ListNode* l, ListNode* r) {
        ListNode* pre = nullptr;
        auto cur = l;
        while(pre != r) {
            auto nxt = cur->next;
            cur->next = pre;
            pre = cur; cur = nxt;
        }
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(!head) return head;
        if(left == right) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        auto pll = dummy;
        auto rr = head;
        for(int i = 0; i < left-1; i++) 
            pll = pll->next; // pll is before left node
        auto ll = pll->next; // ll is left node
        for(int i = 0; i < right-1; i++)
            rr = rr->next; //rr is right node

        auto rr_end = rr->next;
        // reverse between ll and rr
        reverse(ll, rr);
        pll->next = rr;
        ll->next = rr_end;
        return dummy->next;
    }
};

总结：如果迭代写法去翻转，碰到可能会修改头节点的情况需要添加一个dummy节点

剑指 Offer 36. 二叉搜索树与双向链表

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

class Solution {
public:
    void build(Node* root, Node* &head, Node* &tail) {
        if(!root) return;
        build(root->left, head, tail);
        if(!head)
            head = tail = root;
        else {
            tail->right = root;
            root->left = tail;
            tail = root;
        }
        build(root->right, head, tail);
    }

    Node* treeToDoublyList(Node* root) {
        if(!root) return nullptr;
        Node* head = nullptr;
        Node* tail = nullptr;
        build(root, head, tail);

        head->left = tail;
        tail->right = head;
        return head;
    }
};

持续更新整理中…