C++

喝醉了Ta的梦,晚安

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        //思路： 1->2->2->1
        //快慢指针找到之间结点 将后面的链表进行逆置 现在用一下CPP的方法
        if(A==nullptr || A->next==nullptr)
            return true;
        stack<int> s;
        //找之间结点
        ListNode* fast = A;
        ListNode* slow = A;
        while(fast && fast->next)
        {
            s.push(slow->val);
            slow = slow->next;
            fast = fast->next->next;
        }
        //如何判断奇数偶数
        if(fast)
            slow = slow->next;
        while(!s.empty() && slow)
        {
            if(s.top()!=slow->val)
            {
                return false;
            }
            s.pop();
            slow = slow->next;
        }
        if(!s.empty() || slow)
        {
            return false;
        }
        return true;
    }
};

发表于 2021-11-26 22:06:37 回复(0)

Spectre_

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        if (A == NULL || A->next == NULL) return true;
        ListNode* slow = A;
        ListNode* fast = A;
        while (fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        ListNode* p;
        while (fast)
        {
            p = fast->next;
            fast->next = slow;
            slow = fast;
            fast = p;
        }
        fast = A;
        while (fast)
        {
            if (fast->val != slow->val) return false;
            fast = fast->next;
            slow = slow->next;
        }
        return true;
    }
};

发表于 2019-10-12 23:53:02 回复(0)

吾生有你

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        Stack<Integer> arr=new Stack<>();
        ListNode B=A;
        while(A!=null){
            arr.push(A.val);
            A=A.next;
        }
        while(!arr.isEmpty()){
            if(arr.pop()==B.val)
                B=B.next;
            else
                return false;
        }
        return true;
    }
}

发表于 2018-06-28 21:07:51 回复(0)

大型火焰

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();
        ListNode a = A;
        while(A!=null)
        {
            stack.push(A.val);
            A = A.next;
        }
        while(!stack.isEmpty())
        {
            if(stack.pop()!=a.val)
                return false;
            else{
                a = a.next;
            }
        }
        return true;
    }
}

发表于 2018-03-26 17:58:10 回复(0)

讲道理的牛肉丸顶呱呱

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode *fast=A,*slow=A;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode *tail=reverseList(slow);
        ListNode *head=A;
        while(tail&&head)
        {
            if(tail->val==head->val)
            {
                tail=tail->next;
                head=head->next;
            }
            else
                return false;
        }
        return true;
    }
    ListNode *reverseList(ListNode *head)
    {
        if(!head||!head->next)return head;
        ListNode *pReverse=reverseList(head->next);
        ListNode *pPrev=head->next;
        pPrev->next=head;
        head->next=NULL;
        return pReverse;
    }
};

发表于 2018-01-17 14:00:25 回复(0)

C/C++

nbgao

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if(A==NULL) 
            return false;
        else if(A->next==NULL)
            return true;
                     ListNode *p = A;
        ListNode *q = A;
        while(p!=NULL && p->next!=NULL)
        {
            p = p->next->next;             q = q->next;             }                  ListNode *s = q->next;         ListNode *t = s->next;                  while(s!=NULL)         {             s->next = q;             q = s;             s = t;             t = t->next;          }                  while(A!=NULL)         {             if(A->val != q->val)                 return false;             else{                 if(A->next != q)                     return true;                 A = A->next;                 q = q->next;             }         }         return true;
    }
};

发表于 2017-11-15 13:16:11 回复(0)

BIG_DAN

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if (A == null) {
            return false;
        }
        if (A.next == null) {
            return true;
        }
        
        ListNode slow = A;
        ListNode quick = A;
        while (quick != null && quick.next != null) {
            quick = quick.next;
            if (quick.next != null) {
                quick = quick.next;
            }
            slow = slow.next;
        }
        
        ListNode p = slow.next;
        ListNode p1 = p.next;
        while (p != null) {
            p.next = slow;
            slow = p;
            p = p1;
            if (p1 != null) {
                p1 = p1.next;
            }
        }
        
        while (A != slow) {
            if (A.val != slow.val) {
                return false;
            }
            if (A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}

发表于 2017-09-14 22:24:27 回复(0)

fight灬奋斗

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        int len=0,mid;
        ListNode *p=A,*q,*pre;
        while(p){
            len++;
            p=p->next;
        }
        p=A;
        mid=len/2+len%2;
        while(mid){
            pre=p;
            p=p->next;
            mid--;
        }
        while(p){
            q=p;
            p=p->next;
            q->next=pre;
            pre=q;
        }
        p=A,q=pre;
        while(p!=q&&p->next!=q&&q->next!=p&&p->val==q->val){
            p=p->next;
            q=q->next;
        }
        if(p==q||(p->next==q&&q->next==p))
            return true;
        else 
            return false;
    }
};

发表于 2016-09-08 21:23:48 回复(0)

ForrestYuan

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        int count=0;  //统计该链表的长度
        int i=0;       //数组下表
        ListNode p=A;  
        while(p!=null){    //开始统计链表长度
            count++;
            p=p.next;
        }
        ListNode t=A;
        int tmp[]=new int[count]; //定义一个长度为count的数组用于保存链表的数据
        while(t!=null){
            tmp[i]=t.val;
            i++;
            t=t.next;
        }
        
        for(int m=0;m< count/2;m++){        
            if(!(tmp[m]==tmp[count-m-1])){     //一旦发现有不相等的就返回false
                return false;
            }
        }
        return true;
    }
}

编辑于 2016-04-16 16:47:25 回复(0)

xuyan505

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        if(A == NULL) return false;
        
        bool flag = true;
        ListNode *firstNode = A;
        ListNode *secondNode = A;
        
        while(secondNode->next != NULL) {
            secondNode = secondNode->next;
        }
        
        while(firstNode < secondNode) {
            if(firstNode->val != secondNode->val) {
                flag = false;
                break;
            }
            firstNode = firstNode->next;
            secondNode = updateSecondNode(A, secondNode);
        }
        return flag;
    }
    
    ListNode* updateSecondNode(ListNode *A, ListNode *secondNode) {
        ListNode *preNode = A;
        while(preNode->next != secondNode) {
           	preNode = preNode->next;
        }
        return preNode;       
    }
};

发表于 2016-04-03 18:43:01 回复(0)

李狗什么

本方法是利用了栈的结构，将源node从中间斩断，后半段放入栈中，通过弹栈的方式与源头开始做比对，本代码可以更简单，这样写的思路更清晰一些。


	importjava.util.*;



	 



	/*



	public class ListNode {



	    int val;



	    ListNode next = null;



	 



	    ListNode(int val) {



	        this.val = val;



	    }



	}*/



	public class PalindromeList {



	    public boolean chkPalindrome(ListNode A) {



	        // write code here



	        Stack<ListNode> s = newStack();



	        int nodeLength = getNodeLength(A);



	        int midIndex = nodeLength/2+nodeLength%2;



	        ListNode head = A;



	        for(inti = 0;i<nodeLength;i++){



	            if(i>=midIndex){



	                s.push(head);



	            }



	            head = head.next;



	        }



	        while(!s.isEmpty()){



	            if(s.pop().val!=A.val){



	                return false;



	            }



	            A = A.next;



	        }



	        return true;



	    }



	     



	    public int getNodeLength(ListNode node){



	        intsize = 0;



	        while(node!=null){



	            node = node.next;



	            size++;



	        }



	        return size;



	    }



	}

发表于 2017-10-20 10:30:31 回复(0)

易水

    
                /*        

                struct ListNode {        

                    int val;        

                    struct ListNode *next;        

                    ListNode(int x) : val(x), next(NULL) {}        

                };*/        

                classPalindromeList {        

                public:        

                    bool chkPalindrome(ListNode* A) {        

                        // write code here        

                        //A为空时false,A为单个节点时true        

                        if(A==NULL){        

                            returnfalse;        

                        }elseif(A->next==NULL){        

                            returntrue;        

                        }        

                        //快慢指针找出中间节点        

                        ListNode* quick=A;        

                        ListNode* slow=A;        

                        while(quick!=NULL&&quick->next!=NULL){        

                            quick=quick->next->next;        

                            slow=slow->next;        

                        }        

                        //将中间节点后的指针反转        

                        ListNode* p=slow->next;        

                        ListNode* p1=p->next;        

                        while(p!=NULL){        

                            p->next=slow;        

                            slow=p;        

                            p=p1;        

                            p1=p1->next;        

                        }        

                //从头、尾指针向中间遍历，判断A是否是回文        

                        while(A!=slow){        

                            if((A->val)!=(slow->val)){        

                                returnfalse;        

                            }else{        

                                if(A->next==slow){        

                                    returntrue;        

                                }        

                                A=A->next;        

                                slow=slow->next;        

                            }        

                        }        

                        returntrue;        

                    }        

                };

编辑于 2015-09-08 17:31:24 回复(3)

小飞侠在北京

思路1：空间O(n) 整个链表遍历两边，开一个栈，第一遍遍历把链表中每个元素push进栈中，这样堆中的元素的pop顺序就是链表的倒序输出；第二遍就开始pop栈中数据，每pop一个数据，就把这个数据跟链表中进行对比，如果相同继续往下走，如果不同返回false。

思路2：空间O(1)，使用快慢指针法，第一步设置一个块指针和一个慢指针，快指针一次走两步，慢指针一次走一步（慢），当快指针下一步为null的时候说明慢指针已经走了一半，这就可以找到中间节点。第二步反转中间链表后面的指针，第三部从头尾向中间扫描，对比每个元素是否相等，如果都相等，则是回文数，否则不是回文数。（下面网友易水给出了代码实现，这里不再叙述）

思路1java伪代码：
public void Palindrome(ListNode head){
Stack  s = new Stack;
//第一遍
p1 = head;    //用于第一遍遍历使用的指针
while(p != null){
    s.push(p.val);
} //第二遍
p2 = head;
while(p != null){
    if(p.val = s.pop()){
    }else{
        return false;
    }
        return true;    
}  }

发表于 2015-09-10 19:18:28 回复(8)

Python

华科平凡

class PalindromeList:
    def chkPalindrome(self, A):
        res=[]
        while A:
            res.append(A.val)
            A = A.next
        return res==res[::-1]

python解法，简单易懂

编辑于 2017-09-12 11:05:43 回复(2)

张鹏宇

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class PalindromeList {

	/**
	 * @param args
	 */
	Stack<Integer> stack = new Stack<Integer>();
	Queue<Integer> queue = new LinkedList<Integer>();
	public boolean chkPalindrome(ListNode A) {
        // write code here
		while(A != null){
			stack.push(A.val);
			queue.add(A.val);
			A = A.next;
		}
		while(!stack.isEmpty()){
			if(!stack.pop().equals(queue.poll())){
				break;
			}
		}
		if(stack.isEmpty()){
			return true;
		}else{
			return false;
		}
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode A = new ListNode(1);
		ListNode B = new ListNode(2);
		ListNode C = new ListNode(2);
		ListNode D = new ListNode(1);
		A.next = B;
		B.next = C;
		C.next = D;
		PalindromeList pa = new PalindromeList();
		boolean p = pa.chkPalindrome(A);
		System.out.println(p);
	}

}

发表于 2016-03-19 19:33:27 回复(2)

UnivNK

先将链表反转，然后判断两个链表相应位置上的值是否相等即可。

 public boolean chkPalindrome(ListNode A) {
        ListNode B = reverseList(A);
        while(A != null){
            if(A.val != B.val){
                return false;
            }
            A = A.next;
            B = B.next;
        }
        return true;
    }
    
   public ListNode reverseList(ListNode head){
       if(head == null){
           return null;
       }
       //直接处理第一个节点
       ListNode newHead = new ListNode(head.val);       
       newHead.next = null;
       ListNode temp = null ;
       //直接从第二个节点开始处理（从第二个节点开始的处理方式一样）
       while(head.next != null){
           temp = new ListNode(head.next.val);
           temp.next = newHead;
           newHead = temp;
           head = head.next;
       }
       return newHead;      
   }

发表于 2016-04-05 10:40:20 回复(0)

wcz2023

***

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        int ***=0;
        ListNode *p = A;
        while(p->next){
            *** += p->val - p->next->val;
            p = p->next;
        }
        return ***==0;
    }
};//*** the world

编辑于 2016-07-26 20:38:37 回复(4)

晓宇大美女~

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();
    	ListNode B = A;
    	int length = 0;
    	while(B!=null){
    		length++;
    		B = B.next;
    	}
    	int halfLength = length/2;
    	while(halfLength!=0){
    		stack.push(A.val);
    		A = A.next;
    		halfLength--;
    	}
    	halfLength = length/2;
    	while(halfLength!=0){
    		if(A.val!=stack.pop())
    			return false;
    		A = A.next;
    		halfLength--;
    	}
		return true;
    }
}

发表于 2016-06-24 00:12:51 回复(0)

已注销

//思路1：采用栈，将链表中的前一半元素压入栈中，然后依次出栈和链表后一半元素比较。注意链表长度奇数还是偶数；见下面参考代码；
//思路2，还有快慢指针方法。
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        // write code here
        if(A == NULL || A->next==NULL) return true;
        int len=Length_of_List(A);
        stack<int> st;
        ListNode* p=A;
        for(int i=1;i<=len/2;i++)
        {
            st.push(p->val);
            p=p->next;
        }
        if(len%2==1) p=p->next;
        while(p!=NULL)
        {
            //int k=st.top();
            if(st.top()!=p->val)
                return false;
            st.pop();
            p=p->next;     
        }
        return true;
    }
    int Length_of_List(ListNode* A)
    {
        if(A==NULL) return 0;
        ListNode* p=A;
        int count=0;
        while(p!=NULL)
        {
            count++;
            p=p->next;
        }
        return count;
    }
};

发表于 2016-08-08 20:41:51 回复(0)

老石基

public class PalindromeList {
    public boolean chkPalindrome(ListNode a) {
        // write code here
        if(a==null)
            return false;
        ListNode mid = a;
        ListNode fast = a;
        ListNode temp = mid;
        while(fast!=null){
            temp = mid;
            mid = mid.next;
            fast = fast.next;  
            if(fast!=null)
            	fast = fast.next;
        }
        if(mid==null)
        	return true;
        temp.next = null;
        ListNode cur = mid.next;
        mid.next = null;
        while(cur!=null){
        	temp = cur.next;
        	cur.next = mid;
        	mid = cur;
        	cur = temp;
        }
        while(a!=null&&mid!=null){
        	if(a.val!=mid.val)
        		return false;
        	a = a.next;
        	mid = mid.next;
        }
        return a==null||a.next==null;
    }
}

发表于 2016-07-01 16:34:57 回复(1)

链表的回文结构

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

***

问题信息

热门推荐

通过挑战的用户

相关试题