题解 | #链表内指定区间反转#

链表内指定区间反转

https://www.nowcoder.com/practice/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==n)
        {
            return head;
        }
        ListNode* pseudo = nullptr;
        pseudo = new ListNode(0);// 注意初始化的方式
        pseudo->next = head;
        ListNode* left = pseudo; //之前就错在 head的位置  head->val 就是第一个元素!
        int cnt = 0;
        while(left!=nullptr)
        {
            if(cnt==m-1)
                break;
            left = left->next;
            cnt++;   
        }

        // cout<<left->val;

        ListNode* right = left;
        while(right!=nullptr)
        {
            right = right->next;
            cnt++;
            if(cnt==n+1)
                break;
        }

        // cout<<right->val;
        // 此时两个指针指向指定区间的 类似head 和尾巴处之后的位置

        cnt = m;
        ListNode* pre = right;
        ListNode* curr = left->next;
        while(cnt<=n)
        {
            ListNode* tmp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = tmp;
            cnt++;
        }

        left->next = pre;

        return pseudo->next;

    }
};

我自己的做法,才意识到 链表默认没有前一个伪结点

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:24
点赞 评论 收藏
分享
07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务