题目
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->3->4->5->NULL 将3插入1->之间 1->3->2->4->5->NULL，然后插入4 1->4->3->2->5->NULL.
最后需要注意当m==1时候需要单独处理head指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
struct ListNode *p=head,*q=head,*temp;
if(m==1)
{
for(int i=0;i<n-m;i++)
{
head=q->next;
q->next=q->next->next;
head->next=p;
p=head;
}
return head;
}
for(int i=0;i<m-2;i++)
{
p=p->next;
}
q=p->next;
for(int i=0;i<n-m;i++)
{
temp=p->next;
p->next=q->next;
q->next=p->next->next;
p->next->next=temp;
}
return head;
}
