中国民政网站医院标准化建设,摩托车建设网站,泉州排名推广,北京赛车网站开发多少钱Given a singly linked list, determine if it is a palindrome. 一开始想用栈#xff0c;但是试来试去发现写不出来遂放弃#xff0c;后来想想再不济可以转换成数组然后分别两头扫#xff0c;但是这样就用了O(n) 的空间#xff0c;再进一步#xff0c;可不可以在链表里模… Given a singly linked list, determine if it is a palindrome. 一开始想用栈但是试来试去发现写不出来遂放弃后来想想再不济可以转换成数组然后分别两头扫但是这样就用了O(n) 的空间再进一步可不可以在链表里模拟呢。思前想后发现是可以的只要把链表的头尾接到一起形成个环然后头指针每次一动1步尾指针每次移动 len - 1 步就行了len 是链表的长度。 这样我实现了算法1 /*** Definition for singly-linked list.* function ListNode(val) {* this.val val;* this.next null;* }*/
/*** param {ListNode} head* return {boolean}*/
var isPalindrome function(head) {if (!head) return true;var tail head;var len 0;while (tail tail.next) {len;tail tail.next;}len;tail.next head;var ring len;while (tail.val head.val) {if (tail head || ring 0) return true;head head.next;ring--;for (var i 0; i len - 1; i) {tail tail.next;}}return false;
}; 这个算法是正确的但是很遗憾TLE 了。头尾相接的做法其实是用取模运算的原理来模拟指针运动可以运用相同原理适当改写程序而避免头尾相接算法2 /*** param {ListNode} head* return {boolean}*/
var isPalindrome function(head) {if (!head) return true;var tail head;var len 0;while (tail tail.next) {len;tail tail.next;}len;var p1 head;var p2 head;var k 1;for (var i 0; i len - k; i) {p2 p2.next;}while (p1 p2 p1.val p2.val) {if (p1 p2 || k len) return true;k;p2 head;for (var i 0; i len - k; i) {p2 p2.next;}p1 p1.next;}return false;
}; 算法12 的区别就是有卵用和没卵用的区别但是貌似头尾相接要更简洁一点但是同样是TLE。 后面看了些提示又想出一个土办法可以copy 一个链表出来然后反转然后两个链表一起遍历对比算法3: /*** Definition for singly-linked list.* function ListNode(val) {* this.val val;* this.next null;* }*/
/*** param {ListNode} head* return {boolean}*/
var reverseList function(head) {if (!head) return null;var prev null;var now head;var next head.nextwhile (now) {now.next prev;prev now;now next;if (next) next next.next;}return prev;
};var copyList function(head) {var p new ListNode(-1);var c p;while (head) {var n new ListNode(head.val);c.next n;c n;head head.next;}return p.next;
}var isPalindrome function(head) {if (!head) return true;var copy copyList(head);var rev reverseList(copy);var p rev;var q head;while (p q) {if (p.val ! q.val) return false;p p.next;q q.next;}return true;
}; 这个是可以accept 的但是是用了O(n) 额外空间那么转换成数组或者字符串两头扫八成也是可以通过的。 最后看了一些答案发现虽然翻转整个链表需要O(n)的额外空间但是翻转一半的话就不需要那么只需要把原链表翻转一半然后两头扫就行关键是怎么找到一半。 要么先扫一遍得到长度再扫一遍取一半。但是有更简洁的办法可以一次遍历就找出中点就是快慢指针。设想一个指针按正常速度遍历链表另一个指针的速度是他的一半那么当正常速度指针遍历结束的时候半速指针刚好在链表的中间利用这个技巧找到链表中点然后从中点开始翻转然后两头扫就可以。算法4: /*** Definition for singly-linked list.* function ListNode(val) {* this.val val;* this.next null;* }*/
/*** param {ListNode} head* return {boolean}*/
var reverseList function(head) {if (!head) return null;var prev null;var now head;var next head.nextwhile (now) {now.next prev;prev now;now next;if (next) next next.next;}return prev;
};var isPalindrome function(head) {if (!head) return true;var fast head;var slow head;var m 1;while (fast) {if (m 0) {slow slow.next;}m (m 1) % 2;fast fast.next;}var tail reverseList(slow);while (head tail) {if (head.val ! tail.val) return false;head head.next;tail tail.next;}return true;}; 利用一个整数变量m 来控制slow 指针的速度fast 每走两步slow走一步。然后reverse 另一半两头扫。整个过程还是很简洁的Accepted。 转载于:https://www.cnblogs.com/agentgamer/p/4907848.html
