NC21 链表内指定区间反转

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=188&&tqId=38555&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode* res = new ListNode(-1);
        res->next = head;
        ListNode *cur = res;
        for(int i = 0;i < m-1;i ++){
            ///用于找到翻转区间的前一个节点
            cur = cur->next;
        }
        ListNode *temp = cur->next;//指向已经翻转的链表的结尾
        for(int i = 0;i < n-m;i ++){
            //头插法翻转
            ListNode* nxt = temp->next;
            temp->next = nxt->next;
            nxt->next = cur->next;
            cur->next = nxt;
        }
        return res->next;
    }
};

Java版本：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        for(int i = 0;i < m - 1;i ++){
            //用于找到翻转区间的前一个节点
            cur = cur.next;
        }
        ListNode temp = cur.next;//指向已经翻转的链表的结尾
        for(int i = 0;i < n-m;i ++){
             //头插法翻转
            ListNode nxt = temp.next;
            temp.next = nxt.next;
            nxt.next = cur.next;
            cur.next =  nxt;
        }
        return res.next;
    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self , head , m , n ):
        # write code here
        res = ListNode(-1)
        res.next = head
        cur = res
        for i in range(m-1):
            #用于找到翻转区间的前一个节点
            cur = cur.next
        temp = cur.next#指向已经翻转的链表的结尾
        for i in range(n - m):
            #头插法翻转
            nxt = temp.next
            temp.next = nxt.next
            nxt.next = cur.next
            cur.next = nxt
        return res.next

JavaScript版本:

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
  */
function reverseBetween( head ,  m ,  n ) {
        // write code here
        let res = new ListNode(-1);
        res.next = head;
        let cur = res;
        for(let i = 0;i < m - 1;i ++){
            //用于找到翻转区间的前一个节点
            cur = cur.next;
        }
        let temp = cur.next;//指向已经翻转的链表的结尾
        for(let i = 0;i < n-m;i ++){
             //头插法翻转
            let nxt = temp.next;
            temp.next = nxt.next;
            nxt.next = cur.next;
            cur.next =  nxt;
        }
        return res.next;    
}
module.exports = {
    reverseBetween : reverseBetween
};