首页 > 试题广场 >

回文链表

[编程题]回文链表

热度指数：29241 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现给定一个链表ListNode* pHead，定义bool代表链表是否为回文，请编写程序。

测试样例：

{1,2,3,2,1}

返回：true

{1,2,3,2,3}

返回：false

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

算法知识视频讲解

查看答案及解析

推荐

九城城主

思路：利用快慢指针，找到中间节点；将慢指针节点的值压入栈，到达中间节点后，依次出栈与后续节点的值比较。特别注意长度奇偶数。

代码如下：

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)

Alandy

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。

《程序员面试金典》程序详解：

http://blog.csdn.net/zdplife/article/category/5799903

递归代码实现：

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

/*用数组方式进行添加的，不过数组扩容速度慢（数组最快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)

drdr

    //将链表的后半部分翻转，然后从开头和中间处分别遍历
    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

华科平凡

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)

Howie59

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)

Java

Cuirassiers

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)

总想有个大offer

不使用额外空间，反转后半部分链表，然后一个指针指向链表头，一个指针指向链表中间，
比较值是否相等，不相等就返回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/C++

ycycywoffer

根据参数链表，以头插法方式建立一个反向的新链表，然后循环比对，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)

Python

Yannyezixin

思路：

利用一个快指针，慢指针。慢指针每次走一步，快指针每次走两步。把慢指针走过的结点入栈

比较栈中结点跟慢指针剩余为走过的结点（特别注意链表长度是奇数还是偶数，如果是奇数，慢指针应该跳过中间结点再进行比较）

# -*- 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)

C/C++

南少201911241210480

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)

Spectre_

/*
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)

C/C++

但求八月九月好运！

//不需要那么复杂，直接转换为字符串，直接判断就可以了
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)

C/C++

Y2ljaXJvcmk=

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

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)

我201810261507240

利用另一个指针，移到最后，进行对比，再删掉最后一个节点。

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)

C/C++

SamcYang

思路：快慢指针 + 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)