当前位置：网站首页>＃yyds干货盘点＃面试必刷TOP101：判断一个链表是否为回文结构

＃yyds干货盘点＃面试必刷TOP101：判断一个链表是否为回文结构

2022-08-06 18:19:00 【51CTO】

1.简述：

描述

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

回文是指该字符串正序逆序完全一致。

数据范围：链表节点数，链表中每个节点的值满足

示例1

输入：

返回值：

示例2

输入：

返回值：

说明：

示例3

输入：

返回值：

说明：

2.代码实现：

       
       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
       
      // n==1，返回true
       
      if (head.next == null){
       
          return true;
       
      }
       
      List<Integer> nums = new ArrayList<Integer>();
       
      // 将链表转换成list
       
      while(head!=null){
       
          nums.add(head.val);
       
          head = head.next;
       
      }
       
      int i = 0;
       
      int j = nums.size()-1;
       
      while(i<j){
       
          // 不等则返回false
       
          // 这边有一个坑，如果不适用equals而使用!=的话，在牛客上对于有负数的测试用例可能会无法通过。
       
          if (!nums.get(i).equals(nums.get(j))){
       
              return false;
       
          }
       
          ++i;
       
          --j;
       
      }
       
      return true;
       
  }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.