力扣-92题反转链表II（C++）- 增设dummyHead

雨点打透心脏的1/2处 2022-09-05 04:08 71阅读 0赞

题目链接：[https://leetcode-cn.com/problems/reverse-linked-list-ii/][https_leetcode-cn.com_problems_reverse-linked-list-ii]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
思路：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 2]

/**
     * 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* reverseBetween(ListNode* head, int left, int right) {
        
            ListNode* dummyHead=new ListNode(-1);
            dummyHead->next=head;
            auto pre=dummyHead,cur=dummyHead->next;
    
            for(int i=0;i<left-1;i++){
        
                pre=cur;
                cur=cur->next;
            }
    
            auto a=pre,b=cur;//保存住，作为之后使用
    
            for(int i=left;i<=right;i++){
        
                auto temp=cur->next;
                cur->next=pre;
                pre=cur;cur=temp;
            }
    
            b->next=cur;
            a->next=pre;
    
            ListNode* result=dummyHead->next;
            delete dummyHead;
    
            return result;
    
            /*
            ListNode* cur=head;
            ListNode* pre=NULL;
    
            for(int i=0;i<left-1;i++){
                pre=cur;
                cur=cur->next;
            }
            auto a=pre,b=pre->next;//当left为1时头节点会发生变化，故此，需增加一个dummy节点
    
            for(int i=left;i<=right;i++){
                ListNode* temp=cur->next;
                cur->next=pre;
                pre=cur;cur=temp;
            }
    
            b->next=cur;
            a->next=pre;
            
            return head;
            */
        }
    };

[https_leetcode-cn.com_problems_reverse-linked-list-ii]: https://leetcode-cn.com/problems/reverse-linked-list-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/9fef582c603b46938c7b82a10af1588a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/7667173360e84214a2c1a4a8ba38130a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 2]: /images/20220829/d78609c6d42540ceb33473d22b4d39b2.png