daily leetcode - reverse-linked-list-ii - !
题目地址
https://leetcode.com/problems/reverse-linked-list-ii/
题目描述
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
思路
很奇怪为何没有倒置链表之一，就来了这个倒置链表之二，不过猜也能猜得到之一就是单纯的倒置整个链表，而这道作为延伸的地方就是倒置其中的某一小段。对于链表的问题，根据以往的经验一般都是要建一个 dummy node，连上原链表的头结点，这样的话就算头结点变动了，我们还可以通过 dummy->next 来获得新链表的头结点。这道题的要求是只通过一次遍历完成，就拿题目中的例子来说，变换的是 2,3,4 这三个点，我们需要找到第一个开始变换结点的前一个结点，只要让 pre 向后走 m-1 步即可，为啥要减 1 呢，因为题目中是从 1 开始计数的，这里只走了 1 步，就是结点 1，用 pre 指向它。万一是结点 1 开始变换的怎么办，这就是我们为啥要用 dummy 结点了，pre 也可以指向 dummy 结点。然后就要开始交换了，由于一次只能交换两个结点，所以我们按如下的交换顺序：
1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 3 -> 2 -> 4 -> 5 -> NULL
1 -> 4 -> 3 -> 2 -> 5 -> NULL
我们可以看出来，总共需要 n-m 步即可，第一步是将结点 3 放到结点 1 的后面，第二步将结点 4 放到结点 1 的后面。这是很有规律的操作，那么我们就说一个就行了，比如刚开始，pre 指向结点 1，cur 指向结点 2，然后我们建立一个临时的结点 t，指向结点 3（注意我们用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系，这可以当作一个规律记下来），然后我们断开结点 2 和结点 3，将结点 2 的 next 连到结点 4 上，也就是 cur->next = t->next，再把结点 3 连到结点 1 的后面结点（即结点 2）的前面，即 t->next = pre->next，最后再将原来的结点 1 和结点 2 的连接断开，将结点 1 连到结点 3，即 pre->next = t。这样我们就完成了将结点 3 取出，加入结点 1 的后方。第二步将结点 4 取出，加入结点 1 的后方，也是同样的操作，这里就不多说了，请大家自己尝试下吧，参见代码如下：
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode *dummy = new ListNode(-1), *pre = dummy;
dummy->next = head;
for (int i = 0; i < m - 1; ++i) pre = pre->next;
ListNode *cur = pre->next;
for (int i = m; i < n; ++i) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = pre->next;
pre->next = t;
}
return dummy->next;
}
};
思路2
考虑取出需要反转的这一小段链表，反转完后再插入到原先的链表中。
以本题为例：
变换的是2,3,4这三个点，那么我们可以先取出2，用front指针指向2，然后当取出3的时候，我们把3加到2的前面，把front指针前移到3，依次类推，到4后停止，这样我们得到一个新链表4->3->2, front指针指向4。
对于原链表来说，有两个点的位置很重要，需要用指针记录下来，分别是1和5，把新链表插入的时候需要这两个点的位置。
用pre指针记录1的位置
当4结点被取走后，5的位置需要记下来
这样我们就可以把倒置后的那一小段链表加入到原链表中
(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
关键点解析
- 链表的基本操作（交换）
- 虚拟节点dummy 简化操作
- 考虑特殊情况 m 是 1 或者 n是链表长度的情况
- 用四个变量记录特殊节点， 然后操作这四个节点使之按照一定方式连接即可。
let midStartNode = null;
let preMidStartNode = null;
let midEndNode = null;
let postMidEndNode = null;
- 注意更新current和pre的位置， 否则有可能出现溢出
代码
语言支持：JS, C++, Python3
JavaScript Code:
/*
* @lc app=leetcode id=92 lang=javascript
*
* [92] Reverse Linked List II
*
* https://leetcode.com/problems/reverse-linked-list-ii/description/
*
* algorithms
* Medium (34.13%)
* Total Accepted: 182.3K
* Total Submissions: 532.8K
* Testcase Example: '[1,2,3,4,5]\n2\n4'
*
* 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
*
*
*/
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function(head, m, n) {
// 虚拟节点，简化操作
const dummyHead = {
next: head
}
let current = dummyHead.next; // 当前遍历的节点
let pre = current; // 因为要反转，因此我们需要记住前一个节点
let index = 0; // 链表索引，用来判断是否是特殊位置（头尾位置）
// 上面提到的四个特殊节点
let midStartNode = null;
let preMidStartNode = null;
let midEndNode = null;
let postMidEndNode = null;
while(current) {
const next = current.next;
index++;
// 对 (m - n) 范围内的节点进行反转
if (index > m && index <= n) {
current.next = pre;
}
// 下面四个if都是边界, 用于更新四个特殊节点的值
if (index === m - 1) {
preMidStartNode = current;
}
if (index === m) {
midStartNode = current;
}
if (index === n + 1) {
postMidEndNode = current;
}
if (index === n) {
midEndNode = current;;
}
pre = current;
current = next;
}
// 两个链表合并起来
(preMidStartNode || dummyHead).next = midEndNode; // 特殊情况需要考虑
midStartNode.next = postMidEndNode;
return dummyHead.next;
};
C++ Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int s, int e) {
if (s == e) return head;
ListNode* prev = nullptr;
auto cur = head;
for (int i = 1; i < s; ++i) {
prev = cur;
cur = cur->next;
}
// 此时各指针指向：
// x -> x -> x -> x -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> x -> x -> x ->
// ^head ^prev ^cur
ListNode* p = nullptr;
auto c = cur;
auto tail = c;
ListNode* n = nullptr;
for (int i = s; i <= e; ++i) {
n = c->next;
c->next = p;
p = c;
c = n;
}
// 此时各指针指向：
// x -> x -> x -> x 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 x -> x -> x ->
// ^head ^prev ^p ^cur ^c
// ^tail
if (prev != nullptr) { // 若指向前一个节点的指针不为空，则说明s在链表中间（不是头节点）
prev->next = p;
cur->next = c;
return head;
} else {
if (tail != nullptr) tail->next = c;
return p;
}
}
};
Python Code:
# 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:
"""采用先翻转中间部分，之后与不变的前后部分拼接的思路"""
# 处理特殊情况
if m == n:
return head
# 例行性的先放一个开始节点，方便操作
first = ListNode(0)
first.next = head
# 通过以下两个节点记录拼接点
before_m = first # 原链表m前的部分
after_n = None # 原链表n后的部分
# 通过以下两个节点记录翻转后的链表
between_mn_head = None
between_mn_end = None
index = 0
cur_node = first
while index < n:
index += 1
cur_node = cur_node.next
if index == m - 1:
before_m = cur_node
elif index == m:
between_mn_end = ListNode(cur_node.val)
between_mn_head = between_mn_end
elif index > m:
temp = between_mn_head
between_mn_head = ListNode(cur_node.val)
between_mn_head.next = temp
if index == n:
after_n = cur_node.next
# 进行拼接
between_mn_end.next = after_n
before_m.next = between_mn_head
return first.next
本文参考自：
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode
评论
