题解 | #链表内指定区间反转#
链表内指定区间反转
http://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
// write code here
struct ListNode *ans = malloc(sizeof(struct ListNode));
ans->next = head;
struct ListNode *mp = ans;
struct ListNode *np = head;
if(m == n) return head;
int i = 0;
//两指针同时移动
for(i=0;i<m;i++){
// np = 1
np = mp;
// mp = 2
mp = mp ->next;
}
// np 下移,与 mp->next交换
for(i=m; i<n; i++){
//分两步 ,第一步去除mp ->next 3
struct ListNode *mid = mp->next;
mp->next = mid->next; //变成了 1 2 4 5
//第二步 在np 处加入 去除的 mid
mid->next = np->next;
np->next = mid; // 1 3 2 4 5 这时 mp = 2,np =1 下次则交换 4
}
return ans->next;
}