[编程题]回文链表.。。。。。。。。。

请编写一个函数，检查链表是否为回文。
给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。
测试样例：
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false

 import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Palindrome {
    public boolean isPalindrome(ListNode pHead) {
        //用于存储一半的链表
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListNode p = pHead;
        if(p.next == null){
            //只有一个节点
            return true;
        }
        ListNode q = p;
        int count = 0;
        while( q.next != null){
            q = q.next;
            count++;
            if(count == 2){
                list.add(p.val);
                p = p.next;
                count=0;
            }
        }
        int len = list.size();
        if(count != 0){
            //偶数节点
            list.add(p.val);
            len++; 
        }
        p = p.next;
        //System.out.println(list);
        while(p != null){
            if(p.val != list.get(len-1)){
                return false;
            }
            len--;
            p = p.next;
        }
        return true;
    }
}

 // Win32Project1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdlib.h>

struct ListNode
{
    int Value;
    ListNode * Next;
};


bool Foo(ListNode * pHead)
{

    if (!pHead) return false;

    ListNode * next = pHead;
    ListNode * temp = NULL;

    while (next != NULL)
    {
        if (!temp)
        {
            temp = (ListNode *)malloc(sizeof(ListNode));
            temp->Next = NULL;
            temp->Value = pHead->Value;
        }
        else
        {
            ListNode * temp1 = (ListNode *)malloc(sizeof(ListNode));
            temp1->Next = temp;
            temp1->Value = next->Value;
            temp = temp1;
        }
        next = next->Next;
    }

    next = pHead;
    while (next != NULL)
    {
        if (next->Value != temp->Value) return false;
        temp = temp->Next;
        next = next->Next;
    }

    return true;

}

int _tmain(int argc, _TCHAR* argv[])
{
    int n = 0;
    ListNode * head = NULL;
    ListNode * next = NULL;
    while (true)
    {
        printf("please enter a num, enter 0 exit:\n");
        scanf_s("%d", &n);
        if (n == 0) break;
        if (!head)
        {
            head = (ListNode *)malloc(sizeof(ListNode));
            head->Next = NULL;
            head->Value = n;
            next = head;
        }
        else
        {
            next->Next = (ListNode *)malloc(sizeof(ListNode));
            next = next->Next;
            next->Next = NULL;
            next->Value = n;
        }
    }
    bool b = Foo(head);
    if (b)
        printf("yes\n");
    else
        printf("no\n");

    return 0;
}

VC++6把scanf_s修改为scanf

详细回答一个问题不容易，如果回答帮助了您，请点下我回答右边的采纳，谢谢。

最简单的是一个循环，一个顺序取索引元素，一个倒叙取元素，判断是否想等，完全想等为true，否则false。当然遍历时只遍历一半数量就行了节省性能