单链表翻转（C++ 实现）

// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
ListNode *reverseBetween(ListNode *head, int m, int n) {
    if(!head) return NULL; 
    if(m >= n) return head;
    if(!head->next) return head;
    
    // dummy head
    ListNode *dh = new ListNode(0);
    dh->next = head;
    
    ListNode *pre = dh;
    ListNode *last = head;
    ListNode *cur = last->next;
    
    for(int i = 1; i < m; i++) {
        pre = pre->next;
        last = last->next;
        cur = cur->next;
    }
    
    for(int i = m; i < n; i++) {
        last->next = cur->next;
        cur->next = pre->next;
        pre->next = cur;
        cur = last->next;
    }
    
    ListNode *ret = dh->next;
    
    delete dh;
    dh = NULL;
    
    return ret;
}

void printList(ListNode *head) {
    ListNode *cur = head;
    int c = 0;
    while(cur) {
        cout<<cur->val<<" ";
        cur = cur->next;
        c ++;
    }
    cout<<"  ||  "<<c<<endl;
}


int main() {  
    ListNode *head = new ListNode(1);
    ListNode *cur = head;
    for(int i = 2; i < 20; i++) {
        ListNode *n = new ListNode(i);
        cur->next = n;
        cur = n;
    }
    
    printList(head);
    ListNode *rh = reverseBetween(head, 2, 3);
    printList(rh);
    
    char c;
    cin>>c;
    
    return 0;
}

 

欢迎关注微信公众号——计算机视觉：