Java教程

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

本文主要是介绍算法基础~链表~从位置m到n逆序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法基础~链表~从位置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逆序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!