Java判断该链表是否为回文结构 |
您所在的位置：网站首页 › 判断是否为回文链表 › Java判断该链表是否为回文结构 |
|
题目描述
给定一个链表，请判断该链表是否为回文结构。 示例1 输入 [1,2,2,1] 返回值 true对于一个回文链表可以发现，当指针节点在对其进行遍历时，走到中间位置就等同于从中间倒着往前走 如 1->2->3->2->1，1->2->2->1 所以可以将中间以后的部分视为前半部分的反转 因此可以将中间以后的部分进行反转，就能得到一个和前半部分相同的链表，这也变成了判断回文结构的条件 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * 对于一个回文链表可以发现，当指针节点在对其进行遍历时，走到中间位置就等同于从中间倒着往前走 * 如 1->2->3->2->1，1->2->2->1 * 所以可以将中间以后的部分视为前半部分的反转 * 因此可以将中间以后的部分进行反转，就能得到一个和前半部分相同的链表，这也变成了判断回文结构的条件 */ public boolean isPail (ListNode head) { if(head == null || head.next == null){ return true; } ListNode fastNode = head; ListNode slowNode = head; while(fastNode != null && fastNode.next != null){ fastNode = fastNode.next.next; slowNode = slowNode.next; } //针对后半段链表 进行反转 ListNode curSlowNode = slowNode.next; ListNode preSlowNode = slowNode; ListNode tempNode = null; while(curSlowNode!=null){ tempNode = curSlowNode.next; curSlowNode.next = preSlowNode; preSlowNode = curSlowNode; curSlowNode = tempNode; } slowNode.next = null; while(preSlowNode!=null){ if(head.val != preSlowNode.val){ return false; } head = head.next; preSlowNode = preSlowNode.next; } return true; } }
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |