判断链表是否是回文链表 Example 1:
1 2 Input: 1 → 2 Output: false
Example 2:
1 2 Input: 1 → 2 → 2 → 1 Output: true
Follow up: Could you do it in O(n) time and O(1) space? (Try to solve this problem in O(N) time and O(1) space. Hint: Reverse part of the linked list.)
1.反转部分链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 const isPalindrome = function (head ) { if (!head || !head.next){ return true ; } if (!head.next.next){ return head.val === head.next.val; } let slow = head; let fast = head; while (fast.next && fast.next.next){ slow = slow.next; fast = fast.next.next; } slow.next = reverseList(slow.next); fast = head; slow = slow.next; while (slow !== null ){ if (fast.val !== slow.val){ return false ; } else { fast = fast.next; slow = slow.next; } } return true ; }; const reverseList = function (head ) { let prev = null ; let save = null ; while (head){ save = head.next; head.next = prev; prev = head; head = save; } return prev; };
2.使用堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 const isPalindrome = function (head ) { if (head === null ) { return true ; } const stack = []; let temp = head; while (head != null ) { stack.push(head.val); head = head.next; } while (temp != null ) { if (temp.val != stack.pop()) { return false ; } temp = temp.next; } return true ; };
3.使用递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 const isPalindrome = function (head ) { return recurse(head); function recurse (node ) { if (node === null ){ return true ; } const isPal = recurse(node.next); if (node.val === head.val){ head = head.next; return isPal; } else { return false ; } } };
4.让链表变成双向的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 const isPalindrome = function (head ) { if (!head){ return true ; } let index = head; index.prev = null ; while (index.next){ index.next.prev = inedx; index = index.next; } while (index !== head){ if (index.val === head.val){ index = index.prev; head = head.next } else { return false ; } } return true ; };