题目形容

反转长度为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);}