[LeetCode]92.Reverse Linked List II

本文主要是介绍[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
*   来源：http://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;}
};

这篇关于[LeetCode]92.Reverse Linked List II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---