判斷是否是回文鏈表；
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode類 the head
* @return bool布爾型
*/
public boolean isPail (ListNode head) {
// write code here
if(head == null || head.next == null)
return false;
ListNode slow = head, fast = head.next;
ListNode prev = null;
while(fast != null && fast.next != null){
ListNode tmp = slow.next;
slow.next = prev;
prev = slow;
slow = tmp;
fast = fast.next.next;
}
// 奇數與偶數分類討論
// 奇數時候，slow停在正中間，（slow位置不滿足，因此這個點與后面鏈表相連），因此要后移一位
// 偶數的時候，slow停在中間靠左邊，（slow位置）
// slow 指標指向的元素永遠是等待處理的元素,指向的位置，都還沒有和前面連起來，指過的位置才已經連起來了，
ListNode l2 = slow;
ListNode l1 = prev;
if(fast == null){
l2 = l2.next;
} else{
l2 = slow.next;
slow.next = prev;
l1 = slow;
}
while(l1 != null && l2 != null){
if(l1.val != l2.val)
return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}
public boolean isPail2(ListNode head) {
// write code here
ArrayList<ListNode> list = new ArrayList<> ();
while(head != null){
list.add(head);
head = head.next;
}
int i = 0, j = list.size() -1;
while( i < j){
if(list.get(i).val != list.get(j).val){
return false;
}
i++;
j--;
}
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/109815.html
標籤：Java