Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
https://leetcode.com/problems/palindrome-linked-list/
?
LeetCode。?
?
?
判斷單鏈表是否為回文,要求時間復雜度O(n),空間復雜度O(1)。
如果對空間復雜度沒有要求,有兩種簡單的做法。
leetcode15?一種是開個數組,把鏈表里的值挨個塞進去,然后雙指針。
還有一種是做一輪遍歷,把單鏈表變成雙鏈表(javasrcipt可以修改實例化的對象), 然后雙指針。
?
時間復雜度O(n),空間復雜度O(1)的解法:
1.第一輪遍歷用快慢指針(快指針每次走兩步,慢指針每次走一步)尋找中點 ->?O(n)
LEETCODE,2.反轉后半段鏈表 ->?O(n/2)
3.比較?->?O(n/2)
合起來時間還是O(n)。
你確定這是easy?
1 /** 2 * Definition for singly-linked list. 3 * function ListNode(val) { 4 * this.val = val; 5 * this.next = null; 6 * } 7 */ 8 /** 9 * @param {ListNode} head 10 * @return {boolean} 11 */ 12 var isPalindrome = function(head) { 13 //find middle 14 var slow = head, fast = head, cacheHead = head; 15 while(fast !== null && fast.next !== null){ 16 slow = slow.next; 17 fast = fast.next.next; 18 } 19 20 //reverse link list 21 var list2Head = new ListNode("head"), tmp; 22 while(slow !== null){ 23 tmp = slow; 24 slow = slow.next; 25 tmp.next = list2Head.next; 26 list2Head.next = tmp; 27 } 28 29 //judge palindrom 30 var list1 = cacheHead, list2 = list2Head.next; 31 for(; list2 !== null; list1 = list1.next, list2 = list2.next){ 32 if(list1.val !== list2.val){ 33 return false; 34 } 35 } 36 return true; 37 };
?
LeetCode Online Judge,?
?
?