Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given1->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.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *reverseList(ListNode *root) { if(!root||!root->next) return root; ListNode *p,*q,*tem; p = root; q = NULL; while(p) { if(!q) { p = p->next; q = root; q->next = NULL; continue; } tem = p; p = p->next; tem->next = q; q = tem; } return q; } ListNode *reverseBetween(ListNode *head, int m, int n) { if(NULL==head||NULL==head->next||m==n) return head; ListNode *mp = head; // the point to the head of list ListNode *np = head; // the tail of list ListNode *mp1; // the head of list ListNode *np1; ListNode *newhead; while(n!=1&&n--) np = np->next; if(m==1&&NULL==np->next) return reverseList(head); if(m==1&&NULL!=np->next) { np1 = np->next; np->next = NULL; newhead = reverseList(head); head->next = np1; return newhead; } while(m!=2&&m--) mp = mp->next; mp1 = mp->next; np1 = np->next; np->next = NULL; reverseList(mp1); mp->next = np; mp1->next = np1; return head; }}; 1. 调用reverseList()时, 尾结点要置NULL, 否则不符合调用规则,程序会超时
2. 考虑情况较多, 均分别处理
~m=n
~m=1, n<len
~m=1, n = len
~n=len
~1<m<n<len