首页 > 试题广场 > 回文链表
[编程题]回文链表
  • 热度指数:27222 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

请编写一个函数,检查链表是否为回文。

给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。

测试样例:
{1,2,3,2,1}
返回:true
{1,2,3,2,3}
返回:false
推荐
思路:利用快慢指针,找到中间节点;将慢指针节点的值压入栈,到达中间节点后,依次出栈与后续节点的值比较。特别注意长度奇偶数。
代码如下:
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        if(pHead == NULL)
            return true;
        stack<int> ss;
        ListNode* p = pHead;
        ListNode* q = pHead;
        ss.push(p->val);
        while(q->next != NULL && q->next->next != NULL)
            {
            p = p->next;
           ss.push(p->val);
            q = q->next->next;
        }
        if(q->next == NULL)                                                    //长度为奇数
            ss.pop();
        p = p->next;
        while(!ss.empty())
            {
            if(ss.top() != p->val)
                break;
            p = p->next;
            ss.pop();
        }
        if(ss.empty())
            return true;
        else
            return false;
    }
};
编辑于 2015-08-18 20:51:02 回复(22)
public class Palindrome {
    public boolean isPalindrome(ListNode pHead){
		ListNode fast = pHead;
		ListNode slow = pHead;
		Stack<Integer> stack = new Stack<Integer>();
		/**
		 * 将链表的前半部分元素装入栈中,当快速runner
                 *(移动的速度是慢速runner的两倍)
		 * 到底链表尾部时,则慢速runner已经处于链表中间位置
		 */
		while(fast != null && fast.next != null){
			stack.push(slow.val);
			slow = slow.next;
			fast = fast.next.next;
		}
		//当链表为奇数个时,跳过中间元素
		if (fast != null) {
			slow = slow.next;
		}
		while(slow != null){
			//如果两者不相同,则该链表不是回文串
			if (stack.pop() != slow.val) {
				return false;
			}
			slow = slow.next;
		}
		return true;
	}
}

发表于 2015-10-02 17:12:23 回复(12)

题目分析:

《方法1》:反转链表

       可以将原始链表反转,判断反转以后的链表与原始链表是否完全一致,如果一致便返回true,如果不一致则返回false。反转链表需要额外的存储空间,不是特别优秀的方法。

《方法2》:栈实现

       我们可以想到从中间节点向两侧开始比较,如果全部相同,则返回true,否则返回false,因为无法获得一个节点的前一个节点,这个时候我们可以想到用栈实现,先将链表前半部分的元素分别压入堆栈,然后在遍历后半部分元素的时候同时和栈顶元素进行比较,如果全部相等则返回true,否则返回false。

      特别注意:因为我们不知道链表的的长度,可以通过快慢指针(一个指针每次移动两个,一个指针每次移动一个)来找到中间元素,这样整体只需要遍历链表一次,所需要的栈空间缩小为方法1的一半。

《方法3》:递归法

       递归方法分为尾部递归和首部递归,还有中间递归,一般的尾部递归都可以用循环来实现,对于我们这道题目,递归的时候无法比较第一个元素和最后一个元素,即使知道最后一个元素,也无法获得最后一个元素的前一个元素。所以我们选择首部递归,先递归直到中间的元素,然后比较中间的元素,把比较结果返回,同时保存后半部分下一个要比较的元素(用引用传递可以,用二级指针也可以),递归返回后,如果是true,则继续比较,如果是false,则直接返回false。
《程序员面试金典》程序详解:
递归代码实现:
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
		ListNode *tail=pHead;
		int length=0;
		while(tail)
		{
			++length;
			tail=tail->next;
		}
		return isPalindrome1(pHead,&tail,length);
    }
	bool isPalindrome1(ListNode* pHead,ListNode **tail,int length)
	{
		if(pHead==NULL||length==0)
			return true;
		if(length==1)
		{
			*tail=pHead->next;
			return true;
		}
		if(length==2)
		{
			*tail=pHead->next->next;
			return pHead->val==pHead->next->val;
		}
		bool sign=isPalindrome1(pHead->next,tail,length-2);
		if(sign==false)
			return false;
		ListNode* tail1=*tail;
		*tail=tail1->next;
		return pHead->val==tail1->val;
	}
};



发表于 2015-09-24 19:34:45 回复(2)
采用递归的方式,将p定义成static:
    每次传入一个新的链表,让p指向链表首节点。
    通过递归,pHead从后往前,p从前往后,同时比较。
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        if(pHead==NULL)
            return true;
        static ListNode* p=NULL;
        if(p==NULL) p=pHead;
        if(isPalindrome(pHead->next)&&(p->val==pHead->val))
        {
            p=p->next;
            return true;
        }
        p=NULL;
        return false;
    }
};

编辑于 2015-09-29 15:55:30 回复(2)
Ron头像 Ron
/*用数组方式进行添加的,不过数组扩容速度慢(数组最快3n),其他用户的快慢指针是一种办法,
虽然复杂度O(n),但是快慢指针更快(2n)*/
public class Palindrome {
 	public boolean isPalindrome(ListNode pHead) {
        // write code here
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	if(pHead == null){
    		return false;
    	}
    	ListNode node = pHead;
    	while(node != null){
            list.add(node.val);
    		node = node.next;
    	}
    	int N = list.size();
    	for(int i = 0;i < N/2; i++){
    		if(list.get(i) != list.get(N-i-1)){
    			return false;
    		}
    	}
    	return true;
    }
}

发表于 2015-08-31 17:04:18 回复(0)
    //将链表的后半部分翻转,然后从开头和中间处分别遍历
    bool isPalindrome(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL) return true;
        //翻转后半部分链表
        ListNode* fast = pHead, *slow = pHead;
        while(fast->next != NULL){
            fast = fast->next;
            if(fast->next != NULL){
                fast = fast->next;
                slow = slow->next;
            }
        }
        while(slow->next != fast){
            ListNode* tmp = slow->next;
            slow->next = tmp->next;
            tmp->next = fast->next;
            fast->next = tmp;
        }
        //分别从中间和后半部分开始遍历
        while(fast != NULL){
            if(fast->val != pHead->val)
                return false;
            fast = fast->next;
            pHead = pHead->next;
        }
        return true;
    }

发表于 2017-08-18 15:29:08 回复(0)

PYthon solution,easy to understand

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        arr=[]
        while pHead:
            arr.append(pHead.val)
            pHead=pHead.next
        return arr==arr[::-1]
发表于 2017-10-01 20:24:51 回复(2)
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) {
        // write code here
        String str = "";
        String str2 = "";
        while(pHead!=null){
            str = str+String.valueOf(pHead.val);
            str2 = String.valueOf(pHead.val)+str2;
            pHead = pHead.next;
        }
        if(str.equals(str2)){
            return true;
        }else{
            return false;
        }
    }
}

发表于 2016-09-29 15:20:08 回复(2)
用一个vector存储,然后从两端遍历并比较

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        vector<int> seq;
        while (pHead) {
            seq.push_back(pHead->val);
            pHead = pHead->next;
        }
        for (int i=0; i<seq.size() / 2; ++i) {
            int j = seq.size() - i - 1;
            if (seq.at(i) != seq.at(j)) { return false; }
        }
        return true;
    }
};


运行时间:4ms

占用内存:612k


发表于 2018-12-24 15:07:02 回复(0)
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) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        int flag = 0;
        while(pHead != null){
            stack.push(pHead.val);
            queue.add(pHead.val);
            pHead = pHead.next;
        }
        while(!stack.isEmpty()){
            if(stack.peek() != queue.peek()){
                return false;
            }
            stack.pop();
            queue.poll();
        }
        return true;
    }
}
使用栈和队列实现功能
发表于 2018-08-28 20:59:45 回复(0)

不使用额外空间,反转后半部分链表,然后一个指针指向链表头,一个指针指向链表中间,
比较值是否相等,不相等就返回false。

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        int count=0;
        ListNode* p=pHead;
        while(p!=NULL){
            p=p->next;
            count++;
        }
        count=count%2==0?count/2:(count/2+1);
        p=pHead;
        for(int i=0;i<count;++i){
            p=p->next;
        }
        ListNode* pre=NULL;
        while(p!=NULL){
            ListNode* temp=p->next;
            p->next=pre;
            pre=p;
            p=temp;
        }
        ListNode* m=pHead;
        while(pre!=NULL&&m!=NULL){
            if(pre->val!=m->val)
                return false;
            pre=pre->next;
            m=m->next;
        }

        return true;
    }
};
发表于 2018-02-11 21:37:40 回复(0)
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) {
        // write code here
        // 快慢指针找到链表中间位置节点
        // 将链表前半部入栈,然后在遍历后半部分时,将元素逐一弹出,进行比较
        // 注意处理链表的奇偶,如果为奇,跳过中间节点
        
        ListNode fast = pHead;
        ListNode slow = pHead;
        Stack<Integer> stack = new Stack<Integer>();
        
        while(fast != null && fast.next != null){
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        
        if (fast != null) {
            slow = slow.next;
        }
        
        while(slow != null){
            if (stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }
}

发表于 2017-05-30 16:00:32 回复(0)
import java.util.*;
//两点关键:快慢指针可以找到中间点,如果快指针不为空,则为奇数个,慢指针此时指向中间点,否则无中间点
//单向链表指针不能往回走,所以通过将前半节打入栈中的方式完成(栈的特性 后进先出)

public class Palindrome {
    public boolean isPalindrome(ListNode pHead) {
        ListNode slow =pHead;
        ListNode fast =pHead;
        Stack<Integer> stack =new Stack<Integer>();
        while(fast!=null&&fast.next!=null ){//找到中间点,并将前半节打入栈中
            stack.push(slow.val);
            slow =slow.next;
            fast =fast.next.next;
        }
        if(fast!=null){
            slow =slow.next;
        }
        while(slow.next!=null){//指针从中间点开始每下移一个,就与栈中取出的值对比
            if(slow.val !=stack.pop()){
                return false;
            }
            slow =slow.next;
        }
        return true;
        
    }
}

发表于 2017-05-17 10:24:44 回复(1)
根据参数链表,以头插法方式建立一个反向的新链表,然后循环比对,C++代码如下
bool isPalindrome(ListNode* pHead) {
	// write code here
	if (pHead == nullptr)
		return false;
	ListNode * p = pHead;
	ListNode * q ;
	ListNode * reverse = new ListNode(0);
	reverse->next = nullptr;
	while (p != nullptr){
		q = new ListNode(p->val);
		q->next = reverse->next;
		reverse->next = q;
		p = p->next;
	}
	p = pHead;
	q = reverse->next;
	while (p != nullptr && q != nullptr){
		if (p->val != q->val)
			return false;
		p = p->next;
		q = q->next;
	}
	return true;
}

发表于 2017-05-14 21:39:18 回复(0)
思路:
利用一个快指针,慢指针。慢指针每次走一步,快指针每次走两步。把慢指针走过的结点入栈
比较栈中结点跟慢指针剩余为走过的结点(特别注意链表长度是奇数还是偶数,如果是奇数,慢指针应该跳过中间结点再进行比较
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        if not pHead or not pHead.next:
            return False
        
        stack = []
        slow = pHead
        fast = pHead.next
        
        stack.append(slow.val)
        while True:
            # 链表是偶数长度
            if not fast.next:
                mid = slow.next
               	break
            elif fast.next and not fast.next.next:
                mid = slow.next.next
                break
            slow = slow.next
            fast = fast.next.next
            stack.append(slow.val)
        
        while stack and mid:
            top = stack.pop()
            if top != mid.val:
                return False
            mid = mid.next
       	return True

发表于 2016-08-02 10:53:45 回复(0)
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        vector<int> a;
        while(pHead)
        {
            a.push_back(pHead->val);
            pHead=pHead->next;
        }
        for(int i=0;i<a.size()/2+1;i++)
        {
            if(a[i]!=a[a.size()-1-i])
                return false;
        }
        return true;
    }
};
可以把链表的值传入数组,利用数组进行判断链表是否为回文链表
发表于 2020-03-04 12:37:54 回复(0)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        if (pHead == NULL || pHead->next == NULL) return true;
        ListNode* slow = pHead;
        ListNode* fast = pHead;
        while (fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        stack<int> stk;
        while (fast)
        {
            stk.push(fast->val);
            fast = fast->next;
        }
        slow = pHead;
        while (!stk.empty())
        {
            if (stk.top() != slow->val) return false;
            stk.pop();
            slow = slow->next;
        }
        return true;
    }
};

发表于 2019-10-12 23:25:45 回复(0)
//不需要那么复杂,直接转换为字符串,直接判断就可以了
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr)
            return true;
        string str="";
        while(pHead!=nullptr)
        {
            str+=to_string(pHead->val);
            pHead=pHead->next;
        }
        return str==string(str.rbegin(),str.rend());
    }
};

发表于 2019-05-02 15:54:03 回复(0)

快慢指针+反转慢链一把梭.
用了快慢指针就强迫症不想用栈.

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        if(!pHead) return true;
        ListNode* slow = pHead;
        ListNode* fast = slow;
        ListNode *tmp = nullptr;
        ListNode *last = nullptr;
        while (slow && fast && fast->next) {
            fast = fast->next->next;
            tmp = slow;
            slow = slow->next;
            tmp->next = last;
            last = tmp;
        }
        if (fast) slow = slow->next;
        while(slow && last) {
            if(slow->val != last->val) return false;
            slow = slow->next;
            last = last->next;
        }
        return true;
    }
};
编辑于 2019-02-27 23:15:36 回复(0)
利用另一个指针,移到最后,进行对比,再删掉最后一个节点。

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        if(pHead==NULL)return true;
        while(pHead!=NULL){
            ListNode*pTail=pHead;
            if((pTail->next)==NULL)return true;
            while((pTail->next->next)!=NULL)pTail=pTail->next;
            if((pTail->next->val)!=(pHead->val))return false;
            pTail->next=NULL;
            pHead=pHead->next;
        }
        return true;
    }
};

发表于 2018-10-30 19:33:26 回复(0)
思路:快慢指针 + stack
注意:需要考虑链表的奇偶情况

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        if (NULL == pHead) {
            return false;
        }
        ListNode *faster = pHead;
        ListNode *later = pHead;
        stack<int> staInt;
        while (NULL != faster->next && NULL != faster->next->next) {
            staInt.push(later->val);
            later = later->next;
            faster = faster->next->next;
        }
        if (NULL != faster->next) {
            staInt.push(later->val);
        }
        later = later->next;
        while (!staInt.empty()) {
            if (later->val != staInt.top()) {
                return false;
            }
            later = later->next;
            staInt.pop();
        }
        return true;
    }
};
发表于 2018-04-25 23:04:24 回复(0)