每天一道leetcode234-迴文鏈表
- 2019 年 10 月 4 日
- 筆記
題目
leetcode234-迴文鏈表中文鏈接： https://leetcode-cn.com/problems/palindrome-linked-list/ 英文鏈表： https://leetcode.com/problems/palindrome-linked-list/ 難度：easy 分類：鏈表
題目詳述
請判斷一個鏈表是否為迴文鏈表。
示例 1:
輸入: 1->2 輸出: false 示例 2:
輸入: 1->2->2->1 輸出: true
題目詳解
距離AC只差一個測試用例的錯誤思路
- 之前應該有看過關於迴文鏈表的一種解法，就是對於鏈表的每個元素依次乘以1,2,3,4…求得一個和sum1;
- 然後就是把這個鏈表反轉，反轉鏈表正好昨天做過哈，每天一道leetcode206-反轉鏈表，直接把程式碼拿來用，得到反轉後的鏈表;
- 然後對於這個反轉後的鏈表，依次遍歷然後對於每個元素依次乘以1,2,3,4…求得一個和sum2;
- 然後比較這個兩個sum值，如果相等，那麼就是迴文鏈表
程式碼
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { int sum1 = 0; if(head == null || head.next == null) return true; int count = 1; ListNode temp = head; while(temp != null) { sum1 += count * temp.val; count += 1; temp = temp.next; } int sum2 = 0; count = 1; head = reverseList(head); temp = head; while(temp != null) { sum2 += count * temp.val; count += 1; temp = temp.next; } if(sum1 == sum2) return true; return false; } public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode pre = head; ListNode pNode = head.next; ListNode next = head; //首先處理前兩個節點； pre.next = null; while(pNode != null) { next = pNode.next; pNode.next = pre; pre = pNode; pNode = next; } return pre; } }
結果，差一個用例沒過，說明這種方法還是有點問題~~~~
正確的思路
- 由於題目說了時間複雜度是O(n),空間複雜度是O(1)，所以不能使用新的空間；
- 思路還是反轉鏈表，不過不是反轉整個鏈表，反轉的是後半部分的鏈表；
- 後半部分的鏈表反轉完畢，然後一個從頭開始遍歷，一個從尾巴開始遍歷，依次比較節點的值是不是一樣，一樣就繼續往下，不一樣直接就返回false.
程式碼
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; int length = 0; ListNode temp = head; while(temp != null) { length++; temp = temp.next; } int halfLength = length / 2; temp = head; for(int i=0;i<halfLength;i++) temp = temp.next; ListNode pre = temp; ListNode pNode = temp.next; ListNode next = pNode; while(pNode != null) { next = pNode.next; pNode.next = pre; pre = pNode; pNode = next; } for(int i=0;i<halfLength;i++) { if(head.val != pre.val) return false; head = head.next; pre = pre.next; } return true; } }
程式碼講解
- 15到20行，遍歷鏈表，求鏈表長度的一半的值
- 22-23行，找到鏈表的中間節點
- 24-33行反轉鏈表
- 34-40行一個從頭，一個從尾巴，依次比較值是否相等，不相等就返回false
- 最後就是返回true
