我要招人

去企业版

首页 > 试题广场 >

判断一个链表是否为回文结构(进阶)

[编程题]判断一个链表是否为回文结构(进阶)

热度指数：1276 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个链表，请判断该链表是否为回文结构。

输入描述:

n 表示链表的长度。
ai 表示链表节点的值

输出描述:

如果为回文结构输出 "true" , 否则输出 "false"。

示例1

输入

5
1 2 3 2 1

输出

true

备注:

算法知识视频讲解

Spectre_

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:08:54 回复(0)

pein531

1.先用快慢指针找到链表的中点(链表节点数为奇数)或上中点(链表节点数为偶数)，在这个过程中记得存下慢指针的前一个位置，便于断链操作；

2.断链后得到左右两个子链表，然后反转右子链表；

3.最后遍历两个子链表，检查元素是否相等。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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, n));
    }
    
    private static boolean isPalindrome(ListNode head, int len) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            dummy = dummy.next;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 得到左右链表
        ListNode left = head;
        ListNode right = len % 2 == 1? slow.next: slow;
        // 断链
        dummy.next = null;
        // 反转右链表
        right = reverse(right);
        // 最后比较两个链表的元素
        while(left != null){
            if(left.val != right.val){
                return false;
            }else{
                left = left.next;
                right = right.next;
            }
        }
        return true;
    }
    
    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

发表于 2021-06-10 23:45:32 回复(1)

Javascript

XJINGUO

let readline = require('readline')
let rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})

let arr = []
rl.on('line', function(data){
arr.push(data)
if(arr.length == 2){
console.log(deal(arr))
arr.length = 0
}
})

function deal(data, arr = []){

let temp = data[1].split(' ').map(Number)
let temps = temp.slice().reverse()

for(let i = 0 ;i<data[0];i++){
if(temps[i] === temp[i]){
continue
}else{
return false
}
}
return true
}

发表于 2021-07-30 22:20:31 回复(0)

牛客887263087号

# include <bits/stdc++.h>
using namespace std;

struct list_node{
int val;
struct list_node * next;
};

list_node * input_list(void)
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}

bool check(list_node * head)
{
//////在下面完成代码
if(head == nullptr)
return true;
if(head->next == nullptr)
return true;
if(head->next->next == nullptr){
if(head->val == head->next->val)
return true;
else
return false;
}
list_node *slow = head->next;
list_node *fast = head->next->next;
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
//此时slow为一般中点或上中点
//对剩下一般进行反转
list_node *pre = nullptr;
list_node *cur = slow->next;
list_node *next = nullptr;
while(cur != nullptr){
next = cur->next;
pre = cur;
cur = next;
}
//head为起点 pre为另一起点
while(pre != nullptr && head != nullptr){
if(pre->val != head->val)
return false;
pre = pre->next;
head = head->next;
}
return true;
}

int main ()
{
int L, R;
list_node * head = input_list();
bool flag = check(head);
if(flag)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;

}

//使用快慢指针来解决问题

如果链表个数为奇数，slow指向中点

如果链表个数为偶数, slow指向上中点

然后使用链表反转来解决问题。

a1 -> a2 -> a3 -> a4 -> a5

中点a4 <- a5

a1 -> a2 -> a3 -> a4

中点 a3 <- a4

然后再判断

发表于 2021-05-15 19:57:02 回复(0)

过儿过过过

比较暴力的方法，水个码

list_node * check(list_node * head)
{
    //////在下面完成代码
    list_node *p1=head;
    stack <list_node *> s;
    while(p1!=NULL)
    {
        s.push(p1);
        p1=p1->next;
    }
    list_node *p2=head;
    while(p2!=NULL)
    {
        p1=s.top();
        if(p1->val!=p2->val)
        {
            cout<<"false";
            return head;
        }
        s.pop();
        p2=p2->next;
    }
    cout<<"true";
    return head;
}

发表于 2020-09-02 20:43:07 回复(0)

牛客997296850号

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int num=sc.nextInt();
int[] n=new int[num];
for(int i=0;i<num;i++){
n[i]=sc.nextInt();
}
boolean flag=true;
int[] n2=new int[num];
int temp=num-1;
for(int j=0;j<num;j++){
n2[j]=n[temp];
temp--;
}
for(int i=0;i<num;i++){
if(n2[i]!=n[i]){
flag=false;
break;
}
}
System.out.println(flag);
}
}

发表于 2020-07-29 15:03:55 回复(0)