Reverse Linked List II
题目:
Reverse a linked list from position m to n.
Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.
分析:
按照正常思路去写,记得找到m - n这一段之后要把他们的首尾断开。
解法:
class Solution {
public:
/**
* @param head: The head of linked list.
* @param m: The start position need to reverse.
* @param n: The end position need to reverse.
* @return: The new head of partial reversed linked list.
*/
ListNode* reverseList(ListNode* head) {
ListNode dummy(0);
dummy.next = head;
while (head->next != NULL) {
ListNode* next = head->next;
head->next = next->next;
next->next = dummy.next;
dummy.next = next;
}
return dummy.next;
}
ListNode *reverseBetween(ListNode *head, int m, int n) {
// write your code here
if (head == NULL || head->next == NULL) {
return head;
}
if (m == n) {
return head;
}
ListNode dummy(0);
dummy.next = head;
ListNode* prevM = &dummy;
ListNode* nextN = &dummy;
for (int i = 0; i < m - 1; i++) {
prevM = prevM->next;
nextN = nextN->next;
}
for (int i = 0; i < n - m + 1; i++) {
nextN = nextN->next;
}
ListNode* sectionHead = prevM->next;
prevM->next = NULL;
ListNode* sectionTail = nextN->next;
nextN->next = NULL;
prevM->next = reverseList(sectionHead);
while (prevM->next != NULL) {
prevM = prevM->next;
}
prevM->next = sectionTail;
return dummy.next;
}
};