LeetCode92. 反转链表 II

爱被打了一巴掌 2022-11-10 14:27 126阅读 0赞

难度：`中等`  
题目描述：

> 给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70 1]  
注意第一个节点和最后一个节点，如果right是最后一个元素，next域要置空！

/** * 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) { 
            if(left==right){ 
                return head;
            }
            ListNode * ans=new ListNode(0);
            ans->next=head;
            ListNode *pre=ans;
            for(int i=0;i<left-1;i++){ 
                pre=pre->next;
            }
            ListNode *cur=pre->next;
            ListNode *tmp=cur->next;
            for(int i=left-1;i<right-1;i++){ 
                cur->next=tmp->next;
                tmp->next=pre->next;
                pre->next=tmp;
                tmp=cur->next;
            }
            if(tmp==NULL){ 
                cur->next=NULL;
            }
            return ans->next;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/f272fbf08b3d48b3947f20e80e72f6c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210318215246337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0,size_16,color_FFFFFF,t_70