专栏首页算法其实很好玩Day1-线性表-链表部分逆置

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

题目

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

给定一个链表头指针,以及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时

五 总结一下吧

线性表中,链表问题主要解题思路:

(1)巧用临时头节点

(2)双指针(也叫快慢指针)

(3)然后就是这道题了,不是什么清奇的思路,就是捋清关键节点之前的关系,顺着写下来即可。

六 你还想有六?还不赶紧动手实现一遍

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 信用卡反欺诈

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强
  • bootstrap-table 父子表 联动表 完整例子

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强
  • kmeans算法初步

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强
  • SpringCloud 2.x学习笔记:11、断路器聚合监控(Hystrix Turbine)(Greenwich版本)

    参考 英文原文:https://stackabuse.com/spring-cloud-turbine/ 中文版:https://www.jb51.net/...

    程裕强
  • .MysqlDataTruncation: Data truncation: Data too long for column 'content' at row 1

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强
  • MysqlDataTruncation: Data truncation: Incorrect string value: '\xF0\x9D\x90\xB6"#...' for column

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强
  • python3多线程趣味详解

    python3的多线程很多人无法理解是怎么运行的,因此本文从程序猿的日常生活出发,写了一个由浅入深的多线程教程,这样子大家就不会觉得陌生了,多线程真的很简单很简...

    机器学习和大数据挖掘
  • AccessDeniedException: /opt/elasticsearch-7.0.0/config/elasticsearch.keystore

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强
  • python有序查找算法:二分法

    二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2...

    机器学习和大数据挖掘
  • com.mysql.jdbc.PacketTooBigException: Packet for query is too large (1146177 > 1048576).

    版权声明:本文为博主原创文章,欢迎转载。 ...

    程裕强

扫码关注云+社区

领取腾讯云代金券