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.
处理这个问题还是挺复杂的,需要考虑很多边界的测试用例。我总体的思路是先用循环标记m前一个节点和n后边一个节点,把n后边的节点首先作为当前逆转节点的pre,然后循环n-m次完成所选节点部分的逆序,然后将标记的m节点前一个节点指向逆序后部分的头节点即可。要考虑各种特殊情况,另外考虑即可。code如下:
class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { if(head==NULL || m<0 || n<0) return head; if(head->next == NULL || m==n) return head; ListNode *head2=NULL,*pre,*cur,*temp=head; for(int i=0; i<n+1; i++) { if(i==m-2) head2=temp; else if(i==m-1) cur=temp; else if(i==n) pre=temp; if(temp!=NULL) temp = temp->next; } for(int i=m;i<n+1;i++) { temp = cur->next; cur->next = pre; pre = cur; cur = temp; } if(m==1) return pre; head2->next = pre; return head; } };
leetcode——Reverse Linked List II 选择链表中部分节点逆序(AC),布布扣,bubuko.com
leetcode——Reverse Linked List II 选择链表中部分节点逆序(AC)
原文:http://blog.csdn.net/dalongyes/article/details/30980045