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.
206. Reverse Linked List的拓展，这里只是反向一个链表中的一部分。先建立一个新list node: dummy，用dummy链接m之前不用反向的node，然后反向m~n的节点，最后在把反向的连接起来。
Java:
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* }
*/
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;
}
}
Python:
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
Python:
class Solution:
def reverseBetween(self, head, m, n):
dummyNode = ListNode(0)
p = dummyNode
q = head for x in range(m - 1):
p.next = q
q = q.next
p = p.next start = None
end = q
next = None
for x in range(m, n + 1):
next = q.next
q.next = start
start = q
q = next p.next = start
end.next = next
return dummyNode.next
C++:
/**
* 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 m, int n) {
ListNode dummy{0};
dummy.next = head; auto *prev = &dummy; for (int i = 0; i < m - 1; ++i) {
prev = prev->next;
} auto *head2 = prev; prev = prev->next;
auto *cur = prev->next; for (int i = m; i < n; ++i) {
prev->next = cur->next; // Remove cur from the list.
cur->next = head2->next; // Add cur to the head.
head2->next = cur; // Add cur to the head.
cur = prev->next; // Get next cur.
} return dummy.next;
}
};
类似题目：
[LeetCode] 206. Reverse Linked List 反向链表