菜鸟笔记
提升您的技术认知

[C++]链表部分翻转

// PartReverse.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;

typedef struct SNode {
    int value;
    SNode *pNext;
    SNode(int v):value(v),pNext(NULL){}
}SNode;

void Print(SNode* head) {
    SNode* p = head->pNext;
    while (p) {
        cout << p->value;
        p = p->pNext;
        if (p)
            cout << "->";
    }
    cout << endl;
}

void Destroy(SNode* head) {
    while (head)
    {
        SNode* p = head;
        head = head->pNext;
        delete p;
    }
}


void PartReverse(SNode *head, int m, int n) {
    SNode* p = head;
    SNode* pNext = NULL;
    int i = 1;
    //找到第m个数的前驱
    while (i < m) {
        p = p->pNext;
        i++;
    }
    //移动结点
    i = 0;
    //记录被交换的第一个结点
    SNode* initNext = p->pNext;
    //pNext指向被交换的第二结点
    pNext = p->pNext->pNext;
    while (i<n-m)
    {
        SNode* pCur = pNext;
        pNext = pNext->pNext;
        //头插法
        pCur->pNext = p->pNext;
        p->pNext = pCur;
        i++;
    }
    //pNext指向被移动最后一个结点的下一结点
    initNext->pNext = pNext;
}

int main()
{
    SNode* head = new SNode(0);
    for (int i = 0; i < 13; i++) {
        SNode* p = new SNode(rand() % 10);
        p->pNext = head->pNext;
        head->pNext = p;
    }
    cout << "Before:\t";
    Print(head);
    PartReverse(head, 6, 9);
    cout << "After:\t";
    Print(head);
    Destroy(head);
    system("pause");
    return 0;
}