题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
题目描述:
给定一个链表,请判断该链表是否为回文结构。
例子: 123321 12321 1 11 此类的即为回文结构
方法一:线性表+双指针
这个方法其实很容易想到,把题目换了,如果不是一条链表判断是否是回文结构,换成是一个数组。
所以我们就可以先遍历一遍链表,然后将里面的值先存放进ArrayList中即可。
那么,我们就很容易想到利用双指针去判断是否是回文结构了!
下面直接给出代码~
public boolean isPail (ListNode head) { if(head == null) return false; if(head.next == null) return true; // 创建一个ArrayList用来存储 ArrayList<Integer> list = new ArrayList<>(); // 将链表全部节点的值按顺序放进list while(head != null){ list.add(head.val); head = head.next; } // 双指针,一个指向起点,一个指向终点! int left = 0, right = list.size()-1; while(left < right){ // 如果不相等,那么则不是回文结构,直接返回false // 这里可能有个疑问,为什么是equals,不能直接!= // 下面顺便安利一个小知识点~ if(!list.get(left).equals(list.get(right))) return false; left++; right--; } return true; }
复杂度分析:
时间复杂度:, 循环遍历次数取决于链表的长度。
空间复杂度:, 使用了线性表的空间,空间大小取决于链表的长度。
Tips:
这里来说一下为什么上面的比较是equals而不是用运算符。细心的人应该会发现,ArrayList中的类型是Integer,是包装类型,而不是基本类型。我们直到包装类型都是对象,所以直接使用运算符进行比较的时候,如果不是同一个对象,那么它会直接返回false。但是这也不是一定的,因为在 Java 8 中,Integer 缓存池的大小默认为 -128~ 127。也就是说,如果你的Integer类型的数字范围在-128~ 127中,那么直接使用运算符进行比较,则它都回去Integer缓存池中找,所以能够直接比较里面的值。超过这个范围则每一次就会new一个新的包装类型出来,直接使用运算符则肯定会返回false。
方法二:利用栈的特性
因为如果链表是回文的,那么将整个链表反转后肯定还是跟原链表是一样的。所以我们就利用栈的先进后出的特性,将整个链表的节点放进栈中,然后进行出栈操作相当于链表反转的作用,再进行依次遍历比较。
public boolean isPail (ListNode head) { if(head == null || head.next == null) return true; // 创建栈 Stack<ListNode> stack = new Stack<>(); ListNode node = head; // 将节点依次放进栈 while(node != null){ stack.push(node); node = node.next; } // 遍历然后依次比较 while(head != null){ // 如果中途发现不相等了,则直接返回false if(head.val != stack.pop().val) return false; head = head.next; } return true; }
复杂度分析:
时间复杂度:, 循环遍历次数取决于链表的长度。
空间复杂度:, 使用了栈,空间大小取决于链表的长度。
方法三:找中点+反转链表+遍历比较
看到方法的介绍其实就直到这个方法的步骤了,没错就是分为三个步骤!
1、快慢指针找中点
先使用快慢指针找到链表的中点,然后根据中点找到表示后半段链表的头节点。
可以利用 快慢指针,快指针一次走两步,慢指针依次走一步,当快指针走到终点的时候,此时如果链表的长度为偶数时,此时中间节点有两个,慢指针则走到了左端点。反之,慢指针则走到中间节点。(这两种情况在我们这道题目的总代吗,我们可以直接合并为一种,则第二个链表的长度比第一个链表的长度小1)
class Solution { public ListNode middleNode(ListNode head) { if(head == null) return head; ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } if(fast.next == null) // 长度为奇数 return slow; // slow为中点 else return slow.next; // 长度为偶数 slow slow.next为中点 } }
2、反转链表 NC78 反转链表
3、遍历比较public boolean isPail (ListNode head) { if(head == null || head.next == null) return true; // 慢指针 ListNode slow = head; // 快指针 ListNode fast = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } fast = slow.next; // 此时fast则会后半段链表的头结点 slow.next = null; // 置为null ListNode nHead = null; while(fast != null){ nHead = fast.next; fast.next = slow; slow = fast; fast = nHead; } nHead = slow; // 后半段链表反转后的链表 fast = head; // 原来的链表 // 遍历判断是否是回文 while (fast != null && nHead != null) { if (fast.val != nHead.val) { return false; } fast = fast.next; nHead = nHead.next; } return true; }
```
复杂度分析:
时间复杂度:, 循环遍历次数。
空间复杂度:, 没有使用额外的空间。
本专栏记录本人维护的仓库( cs-review.cn )分类刷题解法~