【LeetCode】 92. Reverse Linked List II C语言

LeetCode解题心得，欢迎交流！ 第三日 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if(head == NULL) return NULL;
    
    // create a dummy node to mark the head of this list
    struct ListNode *dummy=(struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next=head;
    
    // make a pointer pre as a marker for the node before reversing
    struct ListNode *pre=dummy;
    int i;
    for(i=0;i<m-1;i++) pre=pre->next;
    
    struct ListNode *start=pre->next;   // a pointer to the beginning of a sub-list that will be reversed
    struct ListNode *then =start->next; // a pointer to a node that will be reversed
    
    // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
    // dummy-> 1 -> 2 -> 3 -> 4 -> 5   尾插法
    
    for(i=m;i<n;i++)
    {
        start->next=then->next; //删除节点
        
        then->next=pre->next;   //从后往前插
        pre->next=then;
        then=start->next;   
    }
    
    return dummy->next;
}