首页 > 试题广场 >

判断一个链表是否为回文结构

[编程题]判断一个链表是否为回文结构
  • 热度指数:2549 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个链表,请判断该链表是否为回文结构。

输入描述:
n 表示链表的长度

ai 表示链表的各个节点的值。


输出描述:
如果为回文结构输出 "true" , 否则输出 "false"。
示例1

输入

4
1 2 2 1

输出

true

备注:

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;
}

发表于 2021-09-12 22:09:55 回复(0)
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;
}

发表于 2020-05-30 13:09:24 回复(0)
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;
}

发表于 2020-05-11 11:47:57 回复(0)
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;
}

发表于 2019-09-16 19:56:51 回复(0)
简单版本:先将链表的节点依次放入到栈中,然后在顺序遍历链表的同时一边弹栈比较
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;
    }
}

发表于 2021-11-13 22:41:50 回复(0)
n = int(input())
arr = list(input().split())
if arr==arr[::-1]:
    print('true')
else:
    print('false')

发表于 2021-06-30 09:49:05 回复(0)
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;
}
两种方法来做,都是使用栈。回文串进栈和出栈的次序是相同的。
发表于 2021-06-15 23:31:43 回复(0)
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);
        }
}

发表于 2021-03-09 11:14:43 回复(0)
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;
    }
}

发表于 2019-10-30 22:14:33 回复(0)
student * check(student * head)
{
    //////在下面完成代码
    student *slow = head;
    student *fast = head;
    while (fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    student *nextnode = NULL;
    while (fast != NULL){
        nextnode = fast->next;
        fast->next = slow;
        slow = fast;
        fast = nextnode;
    }
    //此时,slow到达链表尾部
 
    fast = head;//快回头,此时,慢再
    while (fast != NULL && slow != NULL)
    {
        if (fast->num != slow->num)
        {
            printf("不是回文\n");
            return head;
        }
        slow = slow->next;
        fast = fast->next;
    }
    printf("是回文\n");
    return head;
}
发表于 2019-10-05 21:21:28 回复(0)
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);
	}
}

发表于 2019-09-06 21:46:22 回复(0)