LeetCode，[LeetCode][JavaScript]Palindrome Linked List

2023-11-19 阅读 31 评论 0

摘要：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

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 };