題目描述
請編寫一個函數(shù)，檢查鏈表是否為回文驰凛。
給定一個鏈表ListNode* pHead胸懈，請返回一個bool，代表鏈表是否為回文恰响。
測試樣例：
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false
package Chapter2;
public class Palindrome {
// 題目描述
// 請編寫一個函數(shù)趣钱，檢查鏈表是否為回文。
// 給定一個鏈表ListNode* pHead胚宦，請返回一個bool首有，代表鏈表是否為回文燕垃。
// 測試樣例：
// {1,2,3,2,1}
// 返回：true
// {1,2,3,2,3}
// 返回：false
public boolean isPalindrome(ListNode pHead) {
if(pHead == null){
return true;
}
int length=0;
ListNode pHead1=pHead;
while(pHead1 != null){
length++;
pHead1=pHead1.next;
}
if(length == 1){
return true;
}
ListNode pHead2=pHead;
ListNode pHeadBeforeBegin=null;
ListNode pHeadBeforeEnd=null;
for(int i=0;i<length/2;i++){
if(pHeadBeforeBegin == null){
pHeadBeforeBegin=new ListNode(pHead2.val);
pHeadBeforeEnd=pHeadBeforeBegin;
}else{
ListNode tmp=new ListNode(pHead2.val);
pHeadBeforeEnd.next=tmp;
pHeadBeforeEnd=pHeadBeforeEnd.next;
}
pHead2=pHead2.next;
}
if(length%2 == 1){
pHead2=pHead2.next;
}
ListNode newBegin=new ListNode(-1);
ListNode newEnd=null;
while(pHead2 != null){
ListNode tmp=new ListNode(pHead2.val);
tmp.next=newEnd;
newEnd=tmp;
newBegin.next=tmp;
pHead2=pHead2.next;
}
newBegin=newBegin.next;
while(newBegin != null){
if(newBegin.val != pHeadBeforeBegin.val){
return false;
}
newBegin=newBegin.next;
pHeadBeforeBegin=pHeadBeforeBegin.next;
}
return true;
// write code here
}
public static void main(String[] args){
ListNode myListNode=ListNodeOperation.createListNode();
System.out.println(new Palindrome().isPalindrome(myListNode));
}
}
以下思路非常不錯，具體代碼就不貼了
image.png
