Day1-线性表-链表部分逆置

BUPTrenyi

发布于 2019-07-16 11:40:54

4580

发布于 2019-07-16 11:40:54

文章被收录于专栏：算法其实很好玩

一题目

（链表逆置的问题比较简单，不再赘述，故第一天嘛，搞一个链表逆置升级版）

给定一个链表头指针，以及m，n，且m<=n，将链表从位置m到n逆置，且要求不能申请额外空间

二分析

忽略我拙劣的画功。。。首先不能申请额外空间，我们需要一个更优解，即，原地修改。

首先我们思考，对于部分逆置，我们需要考虑四个关键节点，即：

（1）

逆置段节点的头节点：它是逆置段，逆置后的尾节点，我们称之节点1

逆置段节点的尾节点：它是逆置段，逆置后的头节点，我们称之节点2

逆置段节点的头节点的前驱：它的后继节点，最终指向节点2

同时节点1要连接上后继节点，即连接上，逆置段尾节点的后继

即当输入m=2，n=4时，最终返回1 4 3 2 5

（2）同时留意m的输入，若m=1时，即从头节点开始逆置，应该怎么返回？

（3）最后记得销毁new申请的临时堆栈空间

三完整代码

（给出完整可编译代码并注释）

//
// Created by renyi on 2019/5/29.
//
#include <iostream>
using namespace std;

struct Node{
    int value;
    Node* next;
    Node(int v):value(v),next(NULL){}
};

Node* reverse(Node* head, int m, int n){
    int changeLen = n - m + 1;//需要逆置的节点的个数
    Node* preHead = NULL;//初始化，开始逆置的节点的前驱
    Node* result = head;//该函数最终返回的头节点，非特殊情况就是head

    while (head && --m){
        preHead = head;//将head移动m-1个位置，此时head指向开始逆置的节点
        head = head->next;
    }
    Node* modifyListTail = head;//将modifyListTail，即逆置后尾节点指向head
    Node* newHead = NULL;

    while (head && changeLen){//该函数完成逆置n-m+1个节点
        Node* next = head->next;
        head->next = newHead;
        newHead = head;
        head = next;
        changeLen--;
    }
    modifyListTail->next = head;
    if (preHead){//如果preHead不为空，那么就不是从第一个节点开始逆置的
        preHead->next = newHead;
    }
    else{//如果preHead是空，那就是从第一个节点开始逆置的，那么逆置段中，逆置后的头节点，就是要返回的头节点
        result = newHead;
    }
    return result;
}

void destroy(Node* head){
    Node* next;
    while(head){
        next = head->next;
        delete(head);
        head = next;
    }
}
void print(Node* head){
    while(head){
        cout<<head->value<<"->";
        head = head->next;
    }
    cout<<endl;
}

int main(){
    Node* head = new Node(1);
    for (int i = 0; i < 10; ++i) {
        Node* p = new Node(rand() % 100);
        p->next = head->next;
        head->next = p;
    }
    print(head);
    reverse(head, 10, 11);
    print(head);
    destroy(head);
}

四运行结果

当m = 4，n = 8时