题目

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;
}