list_node * check(list_node * head) { //////在下面完成代码 stack<int> stk; list_node *p = head; while (p) { stk.emplace(p->val); p = p->next; } p = head; while (!stk.empty()) { if (stk.top() != p->val) { cout << "false"; return head; } stk.pop(); p = p->next; } cout << "true"; return head; }
list_node * check(list_node * head) { list_node *s = head, *f = head; while(f->next && f->next->next){ f = f->next->next; s = s->next; } stack<list_node*> S; f = s->next; while(f){ S.push(f); f = f->next; } while(!S.empty()){ if(head->val != S.top()->val){ puts("false"); return NULL; }else{ S.pop(); head = head->next; } } puts("true"); return NULL; }
list_node * check(list_node * head) { //////在下面完成代码 //找到中间节点 if(!head||!head->next) cout << "true" << endl; list_node *slow=head, *fast=head; //先更新快指针,再更新慢指针 while(fast->next && fast->next->next){ fast = fast->next->next; slow = slow->next; } //讲另一半链表存入栈中 stack<list_node*> s; list_node* temp = slow->next; while(temp){ s.push(temp); temp = temp->next; } temp = head; while(!s.empty()){ if(s.top()->val != temp->val){ cout << "false" << endl; return head; } else{ s.pop(); temp = temp->next; } } cout << "true" << endl; return head; }
list_node * check(list_node * head) { //////在下面完成代码 list_node *slow=head; list_node *fast=head; while(fast->next!=NULL && fast->next->next!=NULL) { slow=slow->next; fast=fast->next->next; } fast=slow->next; slow->next=NULL; list_node *nextnode=NULL; while(fast!=NULL){ nextnode=fast->next; fast->next=slow; slow=fast; fast=nextnode; } //此时,slow到达链表尾部 nextnode=slow;//保存最后一个节点,恢复链表用 fast=head;//快回头,此时,慢再 while(fast!=NULL && slow!=NULL) { if(fast->val!=slow->val) { cout<<"false"<<endl; return head; } slow=slow->next; fast=fast->next; } cout<<"true"<<endl; return head; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; this.next = null; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] strList = br.readLine().trim().split(" "); ListNode head = new ListNode(Integer.parseInt(strList[0])); ListNode cur = head; for(int i = 1; i < n; i++){ cur.next = new ListNode(Integer.parseInt(strList[i])); cur = cur.next; } System.out.println(isPalindrome(head)); } private static boolean isPalindrome(ListNode head) { Stack<Integer> stack = new Stack<>(); ListNode cur = head; while(cur != null){ stack.push(cur.val); cur = cur.next; } cur = head; while(cur != null){ if(cur.val != stack.pop()) return false; cur = cur.next; } return true; } }
list_node * check(list_node * head) { //////在下面完成代码 // stack<int> mystack; // list_node* temp = head; // while (temp!=nullptr) // { // mystack.push(temp->val); // temp = temp->next; // } // temp = head; // while (!mystack.empty()) // { // int a = mystack.top(); // mystack.pop(); // if (a != temp->val) // { // cout << "false"; // return nullptr; // } // temp = temp->next; // } // cout << "true"; // return nullptr; if (head == nullptr) { cout << "true"; return nullptr; } int half = n/2; stack<int> mystack; list_node* half_node = head; for (int i=0;i<half;++i) { mystack.push(half_node->val); half_node = half_node->next; } if (n%2==1) // 奇数 { half_node = half_node->next; } while (!mystack.empty()) { if (mystack.top() != half_node->val) { cout << "false"; return nullptr; } mystack.pop(); half_node = half_node->next; } cout << "true"; return nullptr; }两种方法来做,都是使用栈。回文串进栈和出栈的次序是相同的。
import java.io.*; public class Main { public static void main(String[] args)throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); br.readLine(); String[] s=br.readLine().split(" "); int n=s.length; int mid=n/2; boolean res=true; for(int i=0;i<mid;i++){ if(s[i].equals(s[s.length-1-i])){ }else{ res=false; break; } } System.out.println(res); } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException{ BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(input.readLine()); String[] str = input.readLine().split(" "); Node head = createNode(str,n); System.out.print(isPalindrome(head)); } public static boolean isPalindrome(Node head){ if(head==null||head.next==null){ return true; } Stack<Integer> stack = new Stack<>(); Node node = head; while (node!=null){ stack.push(node.val); node = node.next; } node = head; while(node!=null&&!stack.isEmpty()){ if(node.val!=stack.pop()){ return false; } node = node.next; } return true; } public static Node createNode(String[] strings,int n){ Node head = new Node(Integer.parseInt(strings[0])); Node node = head; for(int i=1;i<strings.length;i++){ Node newNode = new Node(Integer.parseInt(strings[i])); node.next = newNode; node = newNode; } return head; } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = scan.nextInt(); } int L = 0; int R = arr.length -1; while(L < R) { if(arr[L] != arr[R]) { System.out.println(false); return; } L++; R--; } System.out.println(true); } }