美文网首页
leetcode 92 反转部分单链表

leetcode 92 反转部分单链表

作者: 吃个小烧饼 | 来源:发表于2018-02-10 05:56 被阅读26次

    先解释一下这个题,就是指定一个范围,把这个范围内的数反转。比如2->1->5->4->3->null,反转(2,4):2->4->5->1->3->null

    首先是要注意限制,那么如果表为空,返回self;而数字上的限制,因为已经说明:

    Note:
    Given m, n satisfy the following condition:
    1 ≤ m ≤ n ≤ length of list.

    所以不用考虑m>n啊之类的问题。于是只用控制一个量,就是m==n,因为m到结尾也最多是m==n,不需要做太多控制。
    代码如下:

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(head == nullptr || m==n)
            return head;
        //快速创建一个,设为0,next指向原链表
        ListNode *newList = new ListNode(0);
        newList->next = head;
        ListNode *pre = newList;
        for(int i = 1; i < m; ++i)
            pre = pre->next;
        ListNode *cur = pre->next;
        ListNode *tmp = nullptr;
        for(int i = 0; i< n - m; ++i) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return newList->next;
    }
    

    我们可以看出,反转链表的核心操作都是中间那4句话,i.e.,后边的指向后边,当前后边的指向前边,前边的指向当前,当前指向后边。

    相关文章

      网友评论

          本文标题:leetcode 92 反转部分单链表

          本文链接:https://www.haomeiwen.com/subject/apcctftx.html