题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
一、CPP
1. 迭代链接反转法：
解题思路:先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。
- 首先，对于链表的问题，根据以往的经验一般都是要建一个dummy node，连上原链表的头结点，这样的话就算头结点变动了，我们还可以通过dummy->next来获得新链表的头结点。
- 设置两个指针：pre指向待逆置段的前一个节点（这就是我们为啥要用dummy结点了，万一是结点1开始变换的，pre也可以指向dummy结点）。cur指向待逆置段的第一个节点。
- 按照以下方法进行逆置
step1：1 -> 2 -> 3 -> 4 -> 5 -> NULL
step2：1 -> 3 -> 2 -> 4 -> 5 -> NULL
step3：1 -> 4 -> 3 -> 2 -> 5 -> NULL
以交换2和3为例，图示交换过程：
原始顺序，当各个指针指向确定后为：
对应代码：ListNode *t = cur->next;之前
对应代码：
cur->next = t->next;
对应代码：
t->next = pre->next;
对应代码：
pre->next = t;
下一轮逆置，重新申请t，指向cur后面，pre和cur指向不变
4.刚开始逆置时涉及两个逆置段节点，故逆置轮数只需要进行n-m趟。n-m趟能逆置n-m+1个节点。
时间复杂度:O(n)。
空间复杂度:O(1)。
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
//创建一个头结点
ListNode *dummy = new ListNode(-1);
ListNode *pre = dummy;
dummy->next = head;
//pre指向要逆置段的前一个
for (int i = 0; i < m - 1; ++i){
pre = pre->next;
}
//cur指针指向需要逆置的第一个结点
ListNode *cur = pre->next;
//
for (int i = m; i < n; ++i){
//一直把t更新为cur后继，以cur为基准
ListNode *t = cur->next;
//把t拆下来插到cur前面
cur->next = t->next;
t->next = pre->next;
pre->next = t;
}
return dummy->next;
}
};
2. 单独取出反转法：
解题思路:思路和1也差不多，就是把待逆置段先拆下来，逆置成功后再接上。设计的指针比较多。
初始状态
指针pre：负责待逆置段逆置之后重新连接
指针t：负责头插法逆置
指针tt：负责移动t和连重新接待逆置段的后面的链表
指针first：负责连接待逆置段的后面的链表，一直指向待逆置的第一个节点待逆置段完成逆置之后的状态
再进行简单的拼接即可。
时间复杂度:O(n)。
空间复杂度:O(1)。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
//添加头节点
ListNode *dummy = new ListNode(-1);
dummy->next = head;
//待逆置段的前一个节点pre
ListNode *pre = dummy;
//走到待逆置的前一个节点
for(int i = 0; i< m-1; i++){
pre = pre->next;
}
ListNode *first = pre->next;
ListNode *t = pre->next;
ListNode *new_head = new ListNode(-1);
//断开
pre->next = NULL;
// cout<<pre->val<<first->val<<t->val<<new_head->val<<endl;
ListNode *tt;
for(int i = 0;i<(n-m+1); i++){
tt = t->next;
//头插法逆置
t->next = new_head->next;
new_head->next = t;
t = tt;
}
//拼接
pre->next = new_head->next;
first->next = tt;
return dummy->next;
}
};
3. 递归反转法：
解题思路:递归折磨人，有兴趣可以了解这篇文章，讲的很好。
时间复杂度:O(n)。
空间复杂度:O(n)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *successor = new ListNode(NULL); // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head->next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode* last = reverseN(head->next, n - 1);
head->next->next = head;
// 让反转之后的 head 节点和后面的节点连起来
head->next = successor;
return last;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head->next = reverseBetween(head->next, m - 1, n - 1);
return head;
}
};
二、Java（迭代链接反转法）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
//创建头节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
//创建pre指针，并指向合适的位置(移动m-1个位置)
ListNode pre = dummy;
for(int i = 0; i<m-1; i++){
pre = pre.next;
}
//创建cur,一直指向待逆置段的第一个节点
ListNode cur = pre.next;
//逆置
for(int i = 0; i<n-m; i++){
//t在cur之后
ListNode t = cur.next;
cur.next = t.next;
t.next = pre.next;
pre.next = t;
}
return dummy.next;
}
}
三、Python（迭代链接反转法）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# 创建头节点
dummy = ListNode(-1)
dummy.next = head
# 创建pre指针，并指向合适的位置(移动m-1个位置)
pre = dummy
for i in range(m-1):
pre = pre.next
# 创建cur,一直指向待逆置段的第一个节点
cur = pre.next
# 逆置
for i in range(n-m):
t = cur.next
cur.next = t.next
t.next = pre.next
pre.next = t
return dummy.next
四、各语言及算法时间复杂度
网友评论