92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
题解：链表中间段逆序；输入一个链表，整数m，整数n，将该链表的第m个节点到第n节点的部分逆序，输出中间段逆序后得到的链表；如图：
image.png
图中表示，当m=3，n=5时，将红色方框处链表逆序，进而输出下面的中间段逆序后的链表。
然后我们来详细的分析下解题思路：
因为要逆序中间段，所以我们可以将上图链表分为三段（如下图）：
image.png
不难看出，第一段有（m-1=2）个节点，第二段有(m-n+1=3)个节点；
head初始指向头结点1；
在head右移1次后，指向了待逆序段的前一个节点，我们用pre_head来对该节点（节点2）地址进行存储；右移2次后change_head对待逆序段的头结点（节点3）地址进行存储，使用就地逆置法将待逆序段逆序，链表逆序方法见Leetcode206：https://www.jianshu.com/p/49de10ac0dd5；最终得到下图：
image.png
pre_head->next = new_head;
change_head->next = head;
将三部分链接在一起，便可得到最终逆置后的链表。
注：我们可以在开始用ListNode *result = head来存储头结点的地址，用于输出最后的整个链表；但是要考虑边界条件，就是当m=1时，头结点参与了逆置，新的链表的头结点为new_head，所以此时，ListNode *result = new_head。
My Solution(C/C++完整实现)：
#include <cstdio>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseBetweenNode(ListNode *head, int begin, int end) {
ListNode *result = head;
ListNode *pre_head = NULL;
int change_len = end - begin + 1;
while (begin - 1) {
pre_head = head;
head = head->next;
begin -= 1;
}
ListNode *change_head = head;
ListNode *new_head = NULL;
while (change_len) {
ListNode *next = head->next;
head->next = new_head;
new_head = head;
head = next;
change_len -= 1;
}
change_head->next = head;
if (pre_head) {
pre_head->next = new_head;
}
else {
result = new_head; // 注：因为当pre_head为NULL时，说明链表是从头结点开始逆置的，直接return时result指向head，所以只能返回从逆置后的链表尾结点开始的链表，所以应该返回new_head;
}
return result;
}
};
int main() {
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
ListNode f(6);
ListNode g(7);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
Solution s;
ListNode *result = s.reverseBetweenNode(&a, 1, 2);
while (result) {
printf("%d->", result->val);
result = result->next;
}
return 0;
}
结果：
2->1->3->4->5->6->7->
My Solution(Python)：
class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
len = n - m + 1
result = head
pre_head = ListNode('')
while head and m - 1:
pre_head = head
head = head.next
m -= 1
new_head = None
modify_list_tail = head
while head and len:
next_p = head.next
head.next = new_head
new_head = head
head = next_p
len -= 1
pre_head.next = new_head
modify_list_tail.next = head
if pre_head.val == '':
return pre_head.next
return result
class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
len = n - m + 1
result = head
pre_head = None
while head and m - 1:
pre_head = head
head = head.next
m -= 1
new_head = None
modify_list_tail = head
while head and len:
next_p = head.next
head.next = new_head
new_head = head
head = next_p
len -= 1
modify_list_tail.next = head
if pre_head == None:
result = new_head
else:
pre_head.next = new_head
return result
Reference:
class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
if head is None or head.next is None or m == n: return head
h = ListNode(-1)
h.next = head
fast = slow = h
for _ in range(n - m + 1):
fast = fast.next
for _ in range(m - 1):
fast = fast.next
slow = slow.next
prev = fast.next
curr = slow.next
while prev != fast:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
slow.next = prev
return h.next
