题目

在这里插入图片描述

题目非常简单，无非就是判断一个没用头结点的指针，是否为回文链表，但是简单的题目往往值得更深的思考。该题目有很多的解法，想要在时间击败百分百的话，不仅仅是代码本身，可能跟电脑还有一定的关系。

全遍历，入数组：

思路很容易想到，第一次遍历完整个链表，一边遍历，一遍把节点入数组并计算长度，最后用数组中的元素判断，规避了指针不能随意访问的难受问题。时间:O(N)，空间:O(N)。

int q[70000];bool isPalindrome(struct ListNode* head){
       struct ListNode* p = head;    int len = 0;    while(p){
           q[len++] = p->val;        p = p->next;    }    for(int i = 1; i <= len/2; i++)        if(q[i] != q[len-i+1]) return false;    return true;}

全遍历，入数组，做双向判断，其实就是对上面一个循环的改动。。

bool isPalindrome(struct ListNode* head) {
       int vals[50001], vals_num = 0;    while (head != NULL) {
           vals[vals_num++] = head->val;        head = head->next;    }    for (int i = 0, j = vals_num - 1; i < j; ++i, --j) {
           if (vals[i] != vals[j]) {
               return false;        }    }    return true;}

快慢指针，链表逆置：

设置快慢指针，都从头开始，快指针走每次走两步，慢指针每次走一步，那么慢指针最后要么到链表的中间元素，要么到元素中间元素的左边元素（这取决于链表长度为奇数还是偶数）。最后将前一段或者后一段逆置，判断。该方法有问题，在逆置完之后，如果在访问链表的话会出问题，因此，还需要将其翻转回来，但是题目没有要求不改变链表，我也就懒得写了，同理，可以在该方法机理上进行优化。实现略去翻转的步骤。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */bool isPalindrome(struct ListNode* head){
       // 特殊情况的排除    if(head == NULL || head->next == NULL)        return true;    if(head->next->next == NULL){
           if(head->val == head->next->val)            return true;        else            return false;    }    struct ListNode *fastp, *slowp;    fastp = head->next->next;    slowp = head->next;    while(fastp && fastp->next != NULL){
           fastp = fastp->next->next;        slowp = slowp->next;    }    struct ListNode *prep, *nextp;    prep = nextp = NULL;    while(head != slowp){
           nextp = head->next;        head->next = prep;        prep = head;        head = nextp;    }    if(fastp != NULL && fastp->next == NULL)        slowp = slowp->next;    while(prep != NULL){
           if(prep->val != slowp->val)            return false;        prep = prep->next;        slowp = slowp->next;    }    return true;}

快慢指针，入半栈：

优化上面的方案，省去了一半的循环，同时防止了链表结构的改变。结果如下，完美。emm，也不是，空间是个问题，不过在这个空间爆炸，时间有限的时代，谁又会在乎那点空间呢。

在这里插入图片描述

#define maxsize 100000bool isPalindrome(struct ListNode* head){
   	if(!head)//判除三种特殊情况 		return true;	if(!head->next)		return true; 	if(!head->next->next)		if(head->val!=head->next->val) return false;		else 								 return true;	struct ListNode *t=head,*q=head,*p=head;	struct ListNode **stack=(struct ListNode **)malloc(sizeof(struct ListNode*)*maxsize);	int top=-1;    stack[++top]=t;	while(p->next&&p->next->next){
   		q=q->next;        stack[++top]=q;		p=p->next->next;	}	if(!p->next){
   //判断奇偶  奇数p->next为空，偶数不为空         for(int i=top;i>=0;i--,q=q->next){
   			if(stack[i]->val!=q->val){
   				return false;			}		}	}	else{
   		q=q->next;		for(int i=top;i>=0;i--,q=q->next){
   			if(stack[i]->val!=q->val)				return false;		}	}	free(stack);    return true;}

链表反转：

思路新颖，可以自己尝试在本子上画一下，画出来是不难理解的。

bool isPalindrome(struct ListNode* head){
       if(head == NULL) return true;    int len = 0;    struct ListNode *p = head;    while(p){
           len++;        p = p->next;    }    if(len == 1) return true;    if(len == 2){
           if(head->val == head->next->val) return true;        else return false;    }    if(len == 3){
           if(head->next->next->val == head ->val) return true;        else return false;    }    int tmp = (len-1)/2, flag = 0;    if(len%2 == 1) flag = 1;    len = (len+1)/2;    p = head;    while(len){
           head = head->next;        len--;    }    struct ListNode *q = p, *r = p->next->next;    p = p->next;    q->next = NULL;    while(tmp){
           p->next = q;        q = p;        p = r;        r = r->next;        tmp--;    }    if(flag == 1) q = q->next;    while(head){
           if(q->val != head->val) return false;        q = q->next, head = head->next;    }    return true;}

转载地址：http://rzcki.baihongyu.com/

你可能感兴趣的文章