LeetCode Notes_#92 Reverse Linked List II（C++,Python）

LeetCode

Contents

题目
思路和解答
思路
解答
C++
Python

题目

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

思路和解答

思路

几个关键节点

关键节点

整体思路

图解

（1）先将指针head移动到开始逆置的节点modify_list_tail
（2) 按照之前#206 Reverse Linked List的做法，将[m,n]这一段逆置
（3）将被逆置的一段和逆置段前驱，逆置段后继连接起来
（4）考虑特殊情况：m=1?
如果是从第一个节点开始逆置，那么最后就不需要连接pre_head了

（5）为什么逆置的最后一个节点不需要考虑？

因为n<=length,之后无论如何还有一个NULL节点，最后还是要把链表和NULL接起来

3.思考：返回结果是什么？

返回的结果的形式是指向链表第一个节点的头指针
如果m!=1,结果是一开始的head,要提前保存；如果m=1，结果是new_head

解答

C++

class Solution { 
public: 
    ListNode* reverseBetween(ListNode* head, int m, int n) { 
        int change_len = n-m+1; 
        ListNode * new_head = NULL; 
        ListNode* result = head; 
        ListNode* pre_head = NULL; 
        ListNode* modify_list_tail = NULL; 
        for(int i=1;i<m;i++){ 
           pre_head = head;//保存逆置段的前驱 
            head=head->next;//将head移动到m节点   
        } 
         modify_list_tail = head; 
        while(change_len&&head){//将逆置段逆置 
            ListNode* next = head->next; 
            head->next = new_head; 
            new_head = head; 
            head = next;//最后一次循环，head就是逆置段的后置 
            change_len--; 
        } 
         
        modify_list_tail->next = head; 
        if (pre_head){ 
            pre_head->next = new_head; 
        } 
        else{ 
            result = new_head; 
        } 
        return result; 
    } 
}; 

4ms,C++的确比较快

一个困惑的点：
问题:16行,new_head是NULL,那么是不是最后的结果会在逆置段和逆置后继之间有一个NULL?
回答:不会，因为22行连接逆置段后继的时候，直接将NULL修改为逆置段后继了

自己编写测试用例，在VS Studio里调试

#include <iostream> 
using namespace std; 
struct ListNode { 
    int val; 
    ListNode *next; 
    ListNode(int x) : val(x), next(NULL) {} 
}; 
class Solution { 
public: 
    ListNode* reverseBetween(ListNode* head, int m, int n) { 
        int change_len = n - m + 1; 
        ListNode * new_head = NULL; 
        ListNode* result = head; 
        ListNode* pre_head = NULL; 
        ListNode* modify_list_tail = NULL; 
        for (int i = 1; i<m; i++) { 
            pre_head = head;//保存逆置段的前驱 
            head = head->next;//将head移动到m节点   
        } 
        modify_list_tail = head; 
        while (change_len&&head) {//将逆置段逆置 
            ListNode* next = head->next; 
            head->next = new_head; 
            new_head = head; 
            head = next;//最后一次循环，head就是逆置段的后置 
            change_len--; 
        } 
 
        modify_list_tail->next = head; 
        if (pre_head) { 
            pre_head->next = new_head; 
        } 
        else { 
            result = new_head; 
        } 
        return result; 
    } 
}; 
 
void main() { 
    ListNode a(1); 
    ListNode b(2); 
    ListNode c(3);  
    ListNode d(4);  
    ListNode e(5); 
    a.next = &b; 
    b.next = &c; 
    c.next = &d; 
    d.next = &e; 
    Solution solve; 
    ListNode *head = solve.reverseBetween(&a, 2, 4); 
    while (head) { 
        printf("%d
", head->val); 
        head = head->next; 
    } 
    system("pause"); 
 
} 

Python

class Solution(object): 
    def reverseBetween(self, head, m, n): 
        """ 
        :type head: ListNode 
        :type m: int 
        :type n: int 
        :rtype: ListNode 
        """ 
        change_len = n-m+1 
        pre_head = None 
        result = head 
         
        for i in range(1,m): 
            pre_head = head 
            head = head.next 
        modify_list_tail = head 
         
        new_head = None 
        while(change_len and head): 
            next = head.next 
            head.next = new_head 
            new_head = head 
            head = next 
            change_len-=1 
        # if modify_list_tail: 
        modify_list_tail.next = head 
         
        if(pre_head): 
            pre_head.next = new_head 
        else: 
            result = new_head 
         
        return result 

32ms