92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL

 

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#include 
struct ListNode* reverseBetween(struct ListNode* head, int m, int n){
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    
    struct ListNode *cur, *prev, *next;
    prev = dummy;
    while(m >1)
    {
        prev = prev->next;
        m--;n--;
    }
    cur = prev->next;
    next = cur->next;

    while (n > 1)
    {
        cur->next = next->next;
        next->next = prev->next;
        prev->next = next;
        next = cur->next;
        n--;
    }
    return dummy->next;
}