[数据结构与算法]线性链表的回文数字判断-----数据结构与算法笔记

一、线性链表的回文数字判断

参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。
相关代码：

#include "stdio.h"
#include "stdlib.h"
//#include "LinkList.h"
#define 	OK		1
#define 	ERROR	0
#define 	TRUE	1
#define		FLASE	0
#define 	OVERFLOW	-2

typedef int Status;
typedef int ElemType;
typedef struct LNode {
	ElemType data;		//数据域(信息域)
	struct LNode *next;	//指针域
} LNode, *LinkList;

Status CreateList_L(LinkList &L);
//构造有头结点的链表L
Status CreateList_L(LinkList &L) {
	LinkList p,q;
	char ch;
	L = (LinkList) malloc (sizeof(LNode));
	L->next = NULL;
	q=L;	//起初为L(头)---->NULL
	while((ch=getchar()) != '\n') {
		p = (LinkList) malloc (sizeof(LNode));
		p->data = ch;
		p->next = NULL;
		q->next = p;
		q = q->next;
	}
	return OK;
}

Status ListTrans_L(LinkList &L,int i);
//在链表L中从第 i 个位置起进行元素转置
Status ListTrans_L(LinkList &L,int i) {
	if(i<=0) return ERROR;
	LinkList trans = (LinkList) malloc (sizeof(LNode));
	if(!trans) exit(OVERFLOW);
	trans=L;
	LNode *Pre=trans;	//Pre为前驱，指向新头结点
	for(int n=0; n<i-1; n++) {
		Pre=Pre->next;	//指针后移直至指向i-1处
	}
	LNode *Cur=Pre->next;	//记录当前Cur
	LNode *Next=Cur->next;	//记录后继Next
	while(Next!=NULL) {
		Cur->next = Next->next;
		Next->next = Pre->next;
		Pre->next = Next;
		Next = Cur->next;
	}
	return OK;
}

Status ListPalinDrome_L(LinkList L);
//判断链表L中存储的数据是否为回文
Status ListPalinDrome_L(LinkList L) {
	LinkList p,fast,mid,slow;
	int i=1;
	fast=L;
	slow=L;
	while(fast->next && fast->next->next) {
		fast = fast->next->next;
		slow = slow->next;
		i++;
	}
	ListTrans_L(L,i);	//从中间位置转置，进行前截与后截判断
	mid = slow->next;
	p = L->next;
	slow = slow->next;
	while(p!=mid) {
		if(p->data == slow->data) {
			p=p->next;
			slow=slow->next;
		} else {
			printf("非回文");
			return ERROR;
		}
	}
	printf("回文");
	return OK;
}

int main(void) {
	LinkList L;
	CreateList_L(L);
	ListPalinDrome_L(L);
	return 0;
}

/*
若一个数字从左边读和从右边读的结果是一模一样的，
我们就称其为回文数。如12321就是一个回文数。
请编写代码，以单链表为存储结构，判断输入的数字是否为回文数。

输入：12321  输出：回文
输入：1231   输出：非回文
*/