題目描述

請判斷一個鏈表是否為回文鏈表。

示例 1:

輸入: 1->2 輸出: false

示例 2:

輸入: 1->2->2->1 輸出: true

進階：
你能否用 O(n) 時間復雜度和 O(1) 空間復雜度解決此題？

解題

思路1：直接利用List的順序存儲性，解題

/*** 思路1：數組存儲法* 時間復雜度O(n),空間復雜度O(n)* @param head* @return*/public boolean isPalindrome1(ListNode head) {List<Integer> list = new ArrayList<Integer>();while(head!=null) {list.add(head.val);head=head.next;}int size = list.size();for(int i=0;i<size/2;i++) {if(list.get(i).intValue() != list.get(size-1-i).intValue() ) {return false;}}return true;}

**思路2：**利用棧的入棧、出棧，改變集合順序原理

public boolean isPalindrome(ListNode head) {Stack<Integer> s = new Stack<>();ListNode cur = head;//將整個鏈表入棧，之后出棧的順序其實就是鏈表的逆序while(cur != null){s.push(cur.val);cur = cur.next;}cur = head;while(!s.isEmpty()){if(s.pop() != cur.val){return false;}cur = cur.next;}return true;}

思路3

/*** 思路3：* 1.快慢指針找到中間節點* 2.反轉后半段鏈表* 3.順序比較鏈表前后半段，都相等則為回文* 時間復雜度O(n)，空間復雜度O(1)* @param head* @return*/public boolean isPalindrome(ListNode head) {if(head == null) {return true;}ListNode slow = head, fast=head, mid=null;while(fast!=null && fast.next!=null) {slow = slow.next;fast = fast.next.next;}mid = slow;ListNode cur = mid, next = mid.next, nNext=null;//鏈表從中間截斷cur.next = null;while (next != null) {nNext = next.next;next.next = cur;cur = next;next = nNext;}while(cur != null) {if(head.val != cur.val) {return false;}head = head.next;cur = cur.next;}return true;}

總結

以上是生活随笔為你收集整理的2019-03-22-算法-进化（回文链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。