『链表模板题』题解 | #链表内指定区间反转#

链表内指定区间反转

http://www.nowcoder.com/questionTerminal/b58434e200a648c589ca2063f1faf58c

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        if( m<1 || n<1 || m>n )
        {
            throw "errorInput";
        }

        if( nullptr==head || nullptr==head->next )
        {
            return head;
        }
        ListNode * dummy=new ListNode( 0x3f3f3f );
        dummy->next=head;

        //表示已经到了第1个节点
        ListNode * pre=dummy;
        ListNode * cur=head;
        int beginLoop=m-1;
        int endLoop=n;
        while( beginLoop-- )
        {
            cur=cur->next;
            pre=pre->next;
            --endLoop;
        }

        ListNode * sentry=nullptr;
        while( endLoop-- )
        {
            ListNode * temp=cur->next;
            cur->next=sentry;
            sentry=cur;
            cur=temp;
        }
        pre->next->next=cur;
        pre->next=sentry;

        ListNode * del=dummy;
        dummy=dummy->next;
        delete del;
        return dummy;
    }
};
全部评论

相关推荐

10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务