【Reverse Linked List II】cpp

题目：

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

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

代码：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

        // virtual begin ListNode

        ListNode dummy(-);

        dummy.next = head;

        // move to the m-1 ListNode

        ListNode *p = &dummy;

        for (int i = ; i < m-; ++i) p = p->next;

        ListNode *prev = p;

        ListNode *curr = p->next;

        for (int i = ; i < n-m; ++i){

            ListNode *tmp = curr->next;

            curr->next = tmp->next;

            ListNode *tmp2 = prev->next;

            prev->next = tmp;

            tmp->next = tmp2;

        }

        return dummy.next;

    }

};

Tips:

这道题的思路沿用我的这一篇日志：http://www.cnblogs.com/xbf9xbf/p/4212159.html

需要考虑几种case:

m=1的情况

n=end的情况

再submit两次，就OK了。

==================================================

第二次过这道题，大体思路一下子没有完全想起来。想了一下之后，回忆起来了翻转列表类似抽书本的例子。就顺着思路把代码写出来了，一次AC。

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

            ListNode* dummpy = new ListNode();

            dummpy->next = head;

            // find start position

            ListNode* start = dummpy;

            for ( int i=; i<m-; i++ ) start = start->next;

            // reverse list between start and end

            ListNode* curr = start->next;

            for ( int i=; i<(n-m); ++i )

            {

                ListNode* tmp = curr->next;

                curr->next = tmp->next;

                tmp->next = start->next;

                start->next = tmp;

            }

            return dummpy->next;

    }

};

巴特西

【Reverse Linked List II】cpp

最新文章

热门文章