关键词:
座右铭:代码虐我千百遍,我待代码如初恋!!!
给定一个单链表的头节点head,请判断该链表是否为回文结构。
- 栈方法特别简单(笔试用)
- 改原链表的方法就需要注意边界了(面试用)
第一种方法:用一个栈来辅助实现,将链表从头结点开始依次压入栈中,之后再从栈顶依次弹出并与原链表一个一个进行比较,,如果相比较的过程全部相同,说明是回文结构,如果有一个比对不上就不是回文结构。因为栈的特征是先进后出的,所以弹出的过程就是逆序的过程。这个方法比较简单,缺点就是费点空间,需要O(N)的空间复杂度
第二中方法:第一种基础上改进一下,同样需要一个栈来辅助实现,但是只需要用到栈的一半空间,所以空间复杂度为O(N/2)。额外申请两个变量,一个快指针和慢指针。让慢指针指向链表右半部分的第一个结点,然后将右半部分压入栈中,再从栈中弹出和左半部分一一比较
第三中方法:不用申请栈,只需要O(1)的空间复杂度。申请一个快指针和慢指针,链表结点个数为奇数的时候慢指针来到中点位置,;偶数个的时候,慢指针来到上中点位置。然后将右半部分链表反转,慢指针指向的结点指向空。此时再让慢指针和快指针分别从最右边和最左边开始一一进行比较。最后返回结果之前一定要将右半部分链表反转回来!!!此方法难点在于难抠边界,但是是最优解,适合面试的时候和面试官聊聊哈哈哈~~~///(v)\\\\\\~~~
package com.harrison.class06;
import java.util.Stack;
public class Code02_IsPalindromeList
public static class Node
public int value;
public Node next;
public Node(int v)
value = v;
// need n extra space
public static boolean isPalindrome1(Node head)
Stack<Node> stack = new Stack<Node>();
Node cur = head;
// 将链表从头结点开始依次压入栈中
while (cur != null)
stack.push(cur);
cur = cur.next;
// 从栈顶依次弹出和链表开始比较
while (head != null)
if (head.value != stack.pop().value)
return false;
head = head.next;
return true;
// need n/2 extra space
public static boolean isPalindrome2(Node head)
if (head == null || head.next == null)
return true;
Node right = head.next;// 慢指针
Node cur = head;// 快指针
while (cur.next != null && cur.next.next != null)
right = right.next;
cur = cur.next.next;
// right 奇数个来到中点位置 偶数个来到下中点位置
Stack<Node> stack = new Stack<>();
// 链表的右半部分依次压入栈中
while (right != null)
stack.push(right);
right = right.next;
// 从栈中依次弹出 和链表左部分依次比较
while (!stack.isEmpty())
if (head.value != stack.pop().value)
return false;
head = head.next;
return true;
// need O(1) extra space
public static boolean isPalindrome3(Node head)
if (head == null || head.next == null)
return true;
Node n1 = head;// 慢指针 n1 -> mid
Node n2 = head;// 快指针 n2 -> end
while (n2.next != null && n2.next.next != null)
n1 = n1.next;
n2 = n2.next.next;
// 慢指针来到中点或者上中点位置 快指针来到终点
n2 = n1.next;// n2 来到右部分第一个结点
n1.next = null;// n1.next -> null
Node n3 = null;
// 右部分反转
while (n2 != null)
n3 = n2.next;// n3 -> save next node
n2.next = n1;// next of right node convert
n1 = n2;// n1 move
n2 = n3;// n2 move
n3 = n1;// n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
// 慢指针从右边开始 快指针从头结点开始 一一比较,任何一个为空就停下来
while (n1 != null && n2 != null)
if (n1.value != n2.value)
res = false;
break;
n1 = n1.next;// left to mid
n2 = n2.next;// right to mid
n1 = n3.next;
n3.next = null;
// 将右部分逆序回来
while (n1 != null)
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
return res;
public static void printLinkedList(Node head)
System.out.print("Linked List:");
while (head != null)
System.out.print(head.value + " ");
head = head.next;
System.out.println();
public static void main(String[] args)
Node head = null;
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
判断一个链表是否是回文结构
importjava.util.Stack;/***判断一个链表是否是回文结构*/publicclassIsPalindrome/***将整个链表放入栈中,依次弹出并和原链表比较,相当于直接把链表反转然后比较,若完全相同则为回文结构**@paramhead链表头结点*@return是否回文结构*/publicb... 查看详情
判断一个链表是否是回文结构
importjava.util.Stack;/***判断一个链表是否是回文结构*/publicclassIsPalindrome/***将整个链表放入栈中,依次弹出并和原链表比较,相当于直接把链表反转然后比较,若完全相同则为回文结构**@paramhead链表头结点*@return是否回文结构*/publicb... 查看详情
判断链表的回文结构(代码片段)
...一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。测试样例链表的回文结构思路分析第一步&... 查看详情
回文链表
...设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。//给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。//测试样例://1->2->2->1//返回:true#include&... 查看详情
六种方法判断链表是否为回文序列(代码片段)
这也是一道不难,但是很经典的链表题,请判断一个链表是否为回文链表。示例1:输入:1->2->2->1输出:true进阶你能否用O(n)时间复杂度和O(1)空间复杂度解决此题?看到这个题你有几种思路解决,经过前面... 查看详情
领扣(leetcode)回文链表个人题解(代码片段)
请判断一个链表是否为回文链表。示例1:输入:1->2输出:false示例2:输入:1->2->2->1输出:true进阶:你能否用 O(n)时间复杂度和O(1)空间复杂度解决此题? 一个最暴力的做法,遍历一次,内容保存在数组内,然后判断是否... 查看详情
234.回文链表palindromelinkedlist
Givenasinglylinkedlist,determineifitisapalindrome.Followup:CouldyoudoitinO(n)timeandO(1)space?判断一个链表是否为回文串思路:1.找到中间点,2.反转后半部分链表,3.判断前半部分与后半部分是否相同/***Definitionforsingly-linkedlist.*publicclassListNode 查看详情
回文链表(代码片段)
请判断一个链表是否为回文链表。示例1:输入:1->2输出:false示例2:输入:1->2->2->1输出:true进阶:你能否用 O(n)时间复杂度和O(1)空间复杂度解决此题? 思路:由于题目说了时间复杂度是O(n),空间复杂度是O(1),所以... 查看详情
随手练——s(n)=o,判断一个链表是否为“回文”(代码片段)
方法一:T(n)=O(n),S(n)=O(n)走完一遍链表,每个值入栈,之后再走一遍链表,和每次弹出的栈顶进行比较。核心:LNode*p=l->next;while(p)s.push(p->data);p=p->next;p=l->next;while(p)if(p->data!=s.top())cout<<"fuck"<<endl;b 查看详情
链表的回文结构
...设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。测试样例:1->2->2->1返回:true1/*2structListNod... 查看详情
判断回文链表(代码片段)
...时存在两个中心点,所以上面这个函数需要传入l和r。而判断一个字符串是不是回文串就简单很多,不需要考虑奇偶情况,只需要「双指针技巧」,从两端向中间逼近即可:boolisPalindrome(strings)intleft=0,right=s.length-1;while(left<right)i... 查看详情
算法练习-第六天(判断一个链表是否为回文结构)(代码片段)
不要再因为那些你不能控制的事情有压力了,要专注于你能控制的事情文章持续更新,可以微信搜索【小奇JAVA面试】第一时间阅读,回复【资料】获取福利,回复【项目】获取项目源码,回复【简历模板】获... 查看详情
算法练习-第六天(判断一个链表是否为回文结构)(代码片段)
不要再因为那些你不能控制的事情有压力了,要专注于你能控制的事情文章持续更新,可以微信搜索【小奇JAVA面试】第一时间阅读,回复【资料】获取福利,回复【项目】获取项目源码,回复【简历模板】获... 查看详情
leetcode234.palindromelinkedlist--判断是否是回文链表,返回中间节点,反转链表(代码片段)
Giventhe head ofasinglylinkedlist,return true ifitisapalindrome.Example1:Input:head=[1,2,2,1]Output:trueExample2:Input:head=[1,2]Output:falseConstraints:Thenumberofnodesinthelistisintherange [ 查看详情
牛客top200---判断一个链表是否为回文结构(java图解)(代码片段)
题目分析这里理解就不难1、首先用快慢指针找到中间节点,循环用while(fast!=null&&fast.next!=null),分奇偶两种情况解释(1)奇数节点,如为3个,执行一次循环,slow和fast指向如下,此时slow已经指向... 查看详情
链表的回文结构(代码片段)
...设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。测试样例:输入:1->2->2->1返回:true代码... 查看详情
回文链表
题目描述请编写一个函数,检查链表是否为回文。给定一个链表ListNode*pHead,请返回一个bool,代表链表是否为回文。测试样例:{1,2,3,2,1}返回:true/*structListNode{intval;structListNode*next;ListNode(intx):val(x),next(NULL){}};*/classPalindrome{public:boo... 查看详情
234.回文链表(代码片段)
请判断一个链表是否为回文链表。示例1:输入:1->2输出:false示例2:输入:1->2->2->1输出:true1importjava.util.ArrayList;23publicclassPalindromeLinkedList4staticclassListNode5intval;6ListNodenext;7ListNode(intx)8val=x;91 查看详情