关于数据结构和算法:PIPIOJ1271-反转链表

题目形容

反转长度为 N 的单链表从地位 L 到 R 的子段。请在常数空间复杂度下应用一趟扫描实现反转。

输出

第一行三个整数 N,L,R,1<=L<=R<=N
接下来 N 个数示意 N 个节点的值

输入

输入反转后的单链表节点值

样例输出

5 2 4
1 2 3 4 5

样例输入

1 4 3 2 5

局部反转链表的状态图演示

• 状态 1

• 状态 2

• 状态 3

• 状态 4

• 状态 5

C++ 参考解答

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

LinkList CreateList(LinkList& L,int n) {L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode* s, * r = L;
    int i = 0, x;
    while (i < n) {scanf("%d", &x);
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = r->next;
        r->next = s;
        r = s;
        i++;
    }
    r->next = NULL;
    return L;
}

void Reverse(LinkList& L,int left,int right) {
    LNode* p=NULL, * q=NULL, * r=NULL,*t=NULL;
    p = L;
    int i = 0;
    while (i < left - 1) {
        p = p->next;
        i++;
    }
    q = p;
    p = p->next;
    q->next = NULL;
    t = p;
    while (i < right) {
        r = p->next;
        p->next = q->next;
        q->next = p;
        p = r;
        i++;
    }
    t->next = r;
}

void PrintList(LinkList L) {
    LNode* p = L->next;
    while (p) {printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LinkList L;
    int N, left, right;
    scanf("%d%d%d", &N, &left, &right);
    CreateList(L,N);
    Reverse(L,left,right);
    PrintList(L);
}