算法 中等 | 36. 翻转链表 II
题目描述
翻转链表中第m个节点到第n个节点的部分。
样例1
输入: 1->2->3->4->5->NULL, m = 2 and n = 4,
输出: 1->4->3->2->5->NULL.
样例2
输入: 1->2->3->4->NULL, m = 2 and n = 3,
输出: 1->3->2->4->NULL.
解题思路
- 创建head.
- 找到m的前一个节点-Pre
- 记录Pre的下一个节点，它会是翻转链的尾部。
- 翻转指定区间的链表，翻到最后一个节点时，把reverseTail.next指向它的next。这样就把翻转链表与之后的链表接起来了。
- 返回dummynode的下一个节点。
java题解
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m >= n || head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++) {
if (head == null) {
return null;
}
head = head.next;
}
ListNode premNode = head;
ListNode mNode = head.next;
ListNode nNode = mNode, postnNode = mNode.next;
for (int i = m; i < n; i++) {
if (postnNode == null) {
return null;
}
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
mNode.next = postnNode;
premNode.next = nNode;
return dummy.next;
}
}
C++题解
using namespace std;
class Solution {
public:
void reverse(ListNode *head) {
ListNode *prev = NULL;
while (head != NULL) {
ListNode *temp = head->next;
head->next = prev;
prev = head;
head = temp;
}
}
ListNode *findkth(ListNode *head, int k) {
for (int i = 0; i < k; i++) {
if (head == NULL) {
return NULL;
}
head = head->next;
}
return head;
}
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode *dummy = new ListNode(-1, head);
ListNode *mth_prev = findkth(dummy, m - 1);
ListNode *mth = mth_prev->next;
ListNode *nth = findkth(dummy, n);
ListNode *nth_next = nth->next;
nth->next = NULL;
reverse(mth);
mth_prev->next = nth;
mth->next = nth_next;
return dummy->next;
}
};
python题解
from lintcode import ListNode
class Solution:
def reverse(self, head):
prev = None
while head != None:
next = head.next
head.next = prev
prev = head
head = next
return prev
def findkth(self, head, k):
for i in xrange(k):
if head is None:
return None
head = head.next
return head
def reverseBetween(self, head, m, n):
dummy = ListNode(-1, head)
mth_prev = self.findkth(dummy, m - 1)
mth = mth_prev.next
nth = self.findkth(dummy, n)
nth_next = nth.next
nth.next = None
self.reverse(mth)
mth_prev.next = nth
mth.next = nth_next
return dummy.next