首页 > 代码库 > 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) {        int i;        ListNode *p, *p1, *p2,*p3,*p4,*tmp;        p = p1 = p2 = p3 = p4 = tmp = NULL;        for (i=1, p=head; p; i++, p=p->next){            if(i==m-1) p1 = p;            if(i==m) p2 = p;            if(i==n) p3 = p;            if(i==n+1) p4 = p;        }        while(p2!=p3){            tmp = p2->next;            p2->next = p4;            p4 = p2;            p2 = tmp;        }        p2->next = p4;        p4 = p2;        if(p1){            p1->next = p4;        } else {            head = p4;        }        return head;    }};

 

Reverse Linked List II