首页 > 代码库 > 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->NULLm = 2 and n = 4,

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

Note:
Given mn 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) 
    {
        if(head==NULL || m==n) return head;
        
        ListNode* p0;
        ListNode* plast;
        ListNode* p1;
        
        if(m==1)
        {
            p0=NULL;
            plast=NULL;
            p1=head;
        }
        else
        {
            p0=head;
            for(int i=1;i<m-1;i++)
                p0=p0->next;
            p1=p0->next;
            plast=p0;
        }
        
        ListNode* pm=p1;
        ListNode* p2;
        for(int i=m;i<=n;i++)
        {
            p2=p1->next;
            p1->next=plast;
            plast=p1;
            p1=p2;
        }
        if(m==1)
        {
            head=plast;
        }
        else
        {
            p0->next=plast;
        }
        pm->next=p1;
        return head;
    }
};