首页 > 试题广场 >

链表的回文结构

[编程题]链表的回文结构
  • 热度指数:56655 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例:
1->2->2->1
返回:true

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
先将链表反转,然后判断两个链表相应位置上的值是否相等即可。
 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)
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)
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)
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) {
    	ListNode p = A;					//指向表头
    	int len = 0;					//记录表长
        while(p != null){
            len ++;
            p = p.next;
        }
        //定义一个长度相同数组保存链表的数据
        int[] a = new int[len];
        for(int i=0; i<len; i++){
        	a[i] = A.val;
        	A = A.next;
        }
        //转化为判断数组回文
        for(int i=0; i<len/2; i++){
        	if(a[i] != a[len-1-i]){
        		return false;
        	}
        }
        return true;
    }
}

//方法二:由于不允许利用额外空间,先找到中间结点,再把中间结点后的链表逆置,再依次比较结点是否相等
import java.util.*;
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
    	ListNode fast = A;				//都指向头结点
    	ListNode slow = A;
    	//找mid结点
    	while(fast != null && fast.next != null){		
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	ListNode nextMid = slow.next;		//mid的下一个结点
    	slow.next = null;		//断链
    	
    	ListNode pre = null;			//标记逆置后的表头
    	ListNode next = null;
    	//逆置
    	while(nextMid != null){
    		next = nextMid.next;
    		nextMid.next = pre;
    		pre = nextMid;
    		nextMid = next;
    	}
    	//依次比较两链表
    	while(A != null && pre != null){
    		if(A.val != pre.val){
    			return false;
    		}
    		A = A.next;
    		pre = pre.next;
    	}
    	return true;
    }
}

编辑于 2017-03-20 14:11:13 回复(1)
//思路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)
/*
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)
/*
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)
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        if (A == nullptr
           || A->next == nullptr) {
            return true;
        }
        
        ListNode* head = A;
        ListNode* last = A;
        ListNode* newLast = A;
        while (last->next) {
            newLast = last;
            last = last->next;
        }
        newLast->next = nullptr;
        if (head->val == last->val
            && chkPalindrome(head->next)) {
            return true;
        }
        return false;
    }
};

发表于 2019-08-07 18:29:05 回复(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)
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)
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)
/*
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)
 要求空间为O(1),那就把链表当数组处理,找到相应下标的节点进行比较
发表于 2016-05-04 11:27:06 回复(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
        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)
/*
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)