leetcode - 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.

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* reverseBetween(ListNode* head, int m, int n) {12         if(head == NULL || m==n) return head;13         ListNode* tp = head;14         ListNode* h = head;15         ListNode* tail,*prev,*cur,*nxt, *before;16         int count = 0;17         18         prev = NULL;19         cur = head;20         nxt = head->next;21         for(int i=1;i
     
      next;25         }26         before = prev; //被逆置的部分之前的那个节点（有可能是空节点，那就说明是从第一个节点开始的逆置）27         tail = cur; //被逆置的部分最终的尾节点28         for(int i=m;i
      
       next = prev;30             prev = cur;31             cur = nxt;32             nxt =nxt->next;33         }34         cur->next = prev; //现在cur指向的是最后一个需要逆置的节点35         if(before == NULL){ //如果before指向的是空节点，那说明头结点需要改变。36             head = cur;37         }38         else{  //否则将“被逆置的部分之前的那个节点”的next指向当前节点（即最后一个需要逆置的节点） 39 　　　　　　  before->next = cur; 40         } 41         tail->next = nxt; //被逆置部分的最后一个节点要连上链表后续的部分 42         return head; 43     } 44 };