首页 > 编程语言 > 详细

算法基础~链表~从位置m到n逆序

时间:2021-07-20 09:14:06      阅读:10      评论:0      收藏:0      [点我收藏+]

算法基础~链表~从位置m到n逆序

1,基础知识:“标志地点”,标志地点前需要先到达地点处!~一般是沿着“已知地点(即有指针指明,例如头指针所指)”慢慢循环移动到达目的地。

2,直接上代码,再解释:

public class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n){
        int len = n - m + 1;
        ListNode* result = head;
        //逆置m~n结点前先标志好逆置结点m前的结点为pre_head,以及标志好m结点为modify_list_tail
        ListNode *pre_head = NULL;
        while(head && --m){
            pre_head = head;
            head = head->next;
        }
        ListNode *modify_list_tail = head;
        //开始逆置m~n结点
        ListNode *new_head = NULL;
        while(head && len){
            ListNode *next = head->next;
            head->next = new_head;
            new_head = head;
            head = next;
            len--;
        }
        modify_list_tail = head;
        //对于特殊情况的判断,是否m=1
        if(pre_head){
            pre_head->next = new_head;
        }
        else{
            result = new_head;
        }
        return result;
    }
}

解释:

技术分享图片

 

技术分享图片

 

技术分享图片

 ps:该过程需要注意的细节是:

(1)逆置m~n结点前,需要先标志好头结点的前驱结点pre_head 和 先标志好 m 结点的位置~ 利用 循环移动--m个位置后,

{pre_head = head; head = head->next;}标志好前驱结点(2 这个结点)pre_head 位置

和 head结点到达 3 (m 结点)这个结点,标志好 modify_list_tail

【因为 逆置后,3 这个结点需要连接 到 6 这个结点,所以 3这个结点需要有指针标志】。

(2)考虑m是否为1。

(3)基础知识:“标志地点”,标志地点前需要先到达地点处!~一般是沿着“已知地点(即有指针指明,例如头指针所指)”慢慢循环移动到达目的地。

 

算法基础~链表~从位置m到n逆序

原文:https://www.cnblogs.com/shan333/p/15032959.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!