[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]范围，反转指定区间的链表。1 ≤ m ≤ n ≤ length of list.不满足条件的话，返回原链表

struct ListNode* reverseList(struct ListNode* head) 
{
    if((head == NULL) || (head->next==NULL))  //链表为空,或只有一个结点（无需反转），直接返回
        return head;

    struct ListNode *pre = NULL;//前一个
    struct ListNode *cur = NULL;//当前
    struct ListNode *ne = NULL;//后一个

    pre = head;         //将前面几个节点的地址依次保存在新定义的结构体指针
    cur = head ->next;

    while(cur) {
        ne = cur->next;  //如果当前节点不为空，则将其指针域赋给ne指针
        cur->next = pre; //直接将两个指针的指向反转
        pre = cur;       //将当前节点赋给pre，将三个指针在链表中的位子都往后移一位
        cur = ne;     
    }
    head->next = NULL;//将原来的第一个节点的指针域赋为空，作为尾节点
    head = pre;      //将原来的尾节点变成新链表的第一个节点
    return head;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) 
{
	/*1.Exception handling*/
    if(!head)
		return NULL;
	if(m <=0 || n<=0 || m>=n)
		return head;

	struct ListNode* headTemp = head;
	int LinkNodeLength = 0;
	struct ListNode* mStartLinkNode = head;
	struct ListNode* nEndLinkNode = NULL;
	struct ListNode* mStartPrivLinkNode = NULL;
	struct ListNode* nEndNextLinkNode = NULL;
	struct ListNode* reverseListNode = NULL;

	int i = 0;

	while(headTemp) {
		LinkNodeLength ++;
		headTemp = headTemp->next;
	}
	if(m>=LinkNodeLength||n>LinkNodeLength) 
		return head;
	/*2.Find the Start of LinkNode,and save the privLinkNode of mStartLinkNode*/
	for(i = 1;i<m;i++) {
		mStartPrivLinkNode = mStartLinkNode;/*Save the privLinkNode of mStartLinkNode*/
		mStartLinkNode = mStartLinkNode->next;
	}
	nEndLinkNode = mStartLinkNode;
	//printf("[%d] value:%d\n",__LINE__,mStartPrivLinkNode->val);/*OK*/
	//printf("[%d] value:%d\n",__LINE__,nEndLinkNode->val);/*OK*/
	for(i = m;i<n;i++) {
		nEndLinkNode = nEndLinkNode->next;
	}
	nEndNextLinkNode = nEndLinkNode->next;/*Save the nEndNextLinkNode of nEndLinkNode*/
	nEndLinkNode->next = NULL;/*For the reverseList*/
	//printf("[%d] value:%d\n",__LINE__,nEndLinkNode->val);
	reverseListNode = reverseList(mStartLinkNode);
	//printf("[%d] value:%d\n",__LINE__,reverseListNode->val);
	mStartLinkNode->next = nEndNextLinkNode;/*第n节点后面一个节点*/
	if(mStartPrivLinkNode) {
		mStartPrivLinkNode->next = reverseListNode;
	}
	else {
		head = reverseListNode;
	}

	return head;

}

全部代码如下：

// LeetCode92-Reverse Linked List II.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
/**
 * Definition for singly-linked list.
 **/
 struct ListNode {
      int val;
      struct ListNode *next;
 };

struct ListNode* CreatLink(int aData[],int len)
 {
     if(!aData)
         return NULL;
     struct ListNode *head = NULL;
     struct ListNode *p = NULL;
     struct ListNode *Link= NULL;
     /*第一个节点*/
     head = (struct ListNode *)malloc(sizeof(struct ListNode));
     head->val = aData[0];
     head->next = NULL;
    // aData ++;
     Link = head; /*保存头结点*/
     int i = 1;

     while(i < len) {
         p = (struct ListNode *)malloc(sizeof(struct ListNode));
         p->val = aData[i];
         head->next = p;
         head = p;
         i ++;
     }

     head->next = NULL;
     return Link;
 }

 void printLink(struct ListNode *head)
 {
     while(head) {
         printf("%d",head->val);
         head = head->next;
     }
     printf("\n");
 }

struct ListNode* reverseList(struct ListNode* head) 
{
    if((head == NULL) || (head->next==NULL))  //链表为空,或只有一个结点（无需反转），直接返回
        return head;

    struct ListNode *pre = NULL;//前一个
    struct ListNode *cur = NULL;//当前
    struct ListNode *ne = NULL;//后一个

    pre = head;         //将前面几个节点的地址依次保存在新定义的结构体指针
    cur = head ->next;

    while(cur) {
        ne = cur->next;  //如果当前节点不为空，则将其指针域赋给ne指针
        cur->next = pre; //直接将两个指针的指向反转
        pre = cur;       //将当前节点赋给pre，将三个指针在链表中的位子都往后移一位
        cur = ne;     
    }
    head->next = NULL;//将原来的第一个节点的指针域赋为空，作为尾节点
    head = pre;      //将原来的尾节点变成新链表的第一个节点
    return head;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) 
{
	/*1.Exception handling*/
    if(!head)
		return NULL;
	if(m <=0 || n<=0 || m>=n)
		return head;

	struct ListNode* headTemp = head;
	int LinkNodeLength = 0;
	struct ListNode* mStartLinkNode = head;
	struct ListNode* nEndLinkNode = NULL;
	struct ListNode* mStartPrivLinkNode = NULL;
	struct ListNode* nEndNextLinkNode = NULL;
	struct ListNode* reverseListNode = NULL;

	int i = 0;

	while(headTemp) {
		LinkNodeLength ++;
		headTemp = headTemp->next;
	}
	if(m>=LinkNodeLength||n>LinkNodeLength) 
		return head;
	/*2.Find the Start of LinkNode,and save the privLinkNode of mStartLinkNode*/
	for(i = 1;i<m;i++) {
		mStartPrivLinkNode = mStartLinkNode;/*Save the privLinkNode of mStartLinkNode*/
		mStartLinkNode = mStartLinkNode->next;
	}
	nEndLinkNode = mStartLinkNode;
	//printf("[%d] value:%d\n",__LINE__,mStartPrivLinkNode->val);/*OK*/
	//printf("[%d] value:%d\n",__LINE__,nEndLinkNode->val);/*OK*/
	for(i = m;i<n;i++) {
		nEndLinkNode = nEndLinkNode->next;
	}
	nEndNextLinkNode = nEndLinkNode->next;/*Save the nEndNextLinkNode of nEndLinkNode*/
	nEndLinkNode->next = NULL;/*For the reverseList*/
	//printf("[%d] value:%d\n",__LINE__,nEndLinkNode->val);
	reverseListNode = reverseList(mStartLinkNode);
	//printf("[%d] value:%d\n",__LINE__,reverseListNode->val);
	mStartLinkNode->next = nEndNextLinkNode;/*第n节点后面一个节点*/
	if(mStartPrivLinkNode) {
		mStartPrivLinkNode->next = reverseListNode;
	}
	else {
		head = reverseListNode;
	}

	return head;

}


int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
    struct ListNode *head1 = NULL;
	struct ListNode *head2 = NULL;
    head1 = CreatLink(a,sizeof(a)/sizeof(int));
	printLink(head1);
	head2 = reverseBetween(head1,2,6);
	printLink(head2);
	getchar();
	return 0;
	return 0;
}