092 - Reverse Linked List II

Reverse Linked List II

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.

Hide Tags

Linked List

Hide Similar Problems

(E) Reverse Linked List

 

写了两种reverse，一种是Reverse Nodes in k-Group跟一样的，不断往yaoreverse的尾节点后面插入前面的节点，

这种写法实际上有点啰嗦，因为要先跑到n点才知道尾节点的位置，然后再从m开始翻转，有些部分是重复访问的。

 

另一种写法是就地翻转，每个指向前一个，第一个指向空，然后把前面后面不用翻转的部分，跟翻转过的连起来就行了，

整个过程没有重叠的部分，相对前一种更好一些。

 

/**
* 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 prev(0);
        prev.next = head;
        if(head && n>m)
        {
            ListNode* pp=&prev;
            ListNode* pm=head;
            int count=1;
            while(count<m)
            {
                pp = pp->next;
                count++;
            }
            pm = pp->next;
           
            count = n-m+1;
            ListNode* pn = pm;
            ListNode* revHead=NULL;
            ListNode* revNext=NULL;
            while(count--)
            {
                revNext = pn->next;
                pn->next = revHead;
                revHead = pn;
                pn = revNext;
            }
           
            pp->next = revHead;
            pm->next = revNext;
        }
        return prev.next;
    }
   

    ListNode* reverseBetweenMN(ListNode* head, int m, int n) {
        ListNode prev(0);
        prev.next = head;
        if(head)
        {
            ListNode* pp=&prev;
            ListNode* pm=head;
            ListNode* pn=head;
            int count=1;
            while(pn->next)
            {
                if(count==m)
                    pm = pn;
                if(count==n)
                    break;
                if(count<m)
                    pp = pn;
                pn = pn->next;
                count++;
            }
            pp->next = reverse(pp, pm, pn);
        }
        return prev.next;
    }
   
    ListNode* reverse(ListNode* prev, ListNode* head, ListNode* endd)
    {
        ListNode* succ = endd->next;
        while(prev->next != endd)
        {
            //move head to end's next
            prev->next = head->next;
            head->next = succ;
            endd->next = head;
           
            //make the moved node as "new next"
            succ = head;
            head = prev->next;
        }
        return prev->next;
    }   

};

0 ms, 4 ms.