983
[LeetCode]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滿足以下條件：
1≤M≤N≤列表的長度。
【分析】
思路1：
前m-1個不變，從第m+1個到第n個，依次刪除，用尾插法插入到第m-1個節點後麵。
第一步把4節點刪除放入2節點之後
第二步把5節點刪除放入2節點之後
【代碼1】
/*********************************
* 日期：2014-01-28
* 作者：SJF0115
* 題號: Reverse Linked List II
* 來源：https://oj.leetcode.com/problems/reverse-linked-list-ii/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
if(m > n || n < 0){
return head;
}
ListNode *tail,*p,*rTail,*pre = NULL;
//添加虛擬頭結點(便於反轉全部)
ListNode *beginNode = (ListNode*)malloc(sizeof(ListNode));
beginNode->next = head;
pre = beginNode;
int index = 1;
//遍曆前m-1個節點
while(pre != NULL && index < m){
pre = pre->next;
index++;
}
tail = pre;
rTail = pre->next;
index = 1;
//刪除第m+1節點開始
while(index < (n-m+1) ){
//刪除p節點
p = rTail->next;
rTail->next = p->next;
//尾插法
p->next = tail->next;
tail->next = p;
index++;
}
return beginNode->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6,7,8,9};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 1;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.reverseBetween(head->next,1,8);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
return 0;
}
【代碼2】
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode *preM, *pre = &dummy;
for (int i = 1; i <= n; ++i) {
//preM 第m-1個節點
if (i == m) preM = pre;
if (i > m && i <= n) {
//刪除head節點
pre->next = head->next;
head->next = preM->next;
//尾插法
preM->next = head;
head = pre; // head has been moved, so pre becomes current
}
pre = head;
head = head->next;
}
return dummy.next;
}
};
最後更新：2017-04-03 12:54:53