LeetCode 234. 回文链表_leetcode 234 js

欢迎关注我的 力扣github仓库，有JavaScript和C++两个版本，每日更新

写在前面： 这题好无语，dev跑的结果和oj平台不一样，害我调试那么久
我是通过快慢指针+后半段反转的方式解决的，也可以快慢指针+前半段反转或者快慢指针+栈 等等方式
C++：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)
            return true;
        ListNode *fast=head,*slow=head;
		while(fast && fast->next) //利用快慢指针找到中间值
        {
            slow=slow->next;
            fast=fast->next->next;
        }

        ListNode *L=new ListNode;   //新建一个链表存放后半部分反转的值
		ListNode *temp;    //用于存放slow的下一个指向，因为头插法会使其丢失
        while(slow)
        {
            temp=slow->next;
            slow->next=L;
            L=slow;
            slow=temp;
        }
        
        while(L && L->next )
        {
            if(head->val!=L->val)
                return false;
            head=head->next;
            L=L->next;
        }
        return true;
    }
};
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

JS:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    var fast=head,slow=head;
    if(!head || !head.next)
        return true;
    while(fast && fast.next){
        slow=slow.next;
        fast=fast.next.next;
    }

    var L=new ListNode,temp;//新建一个链表存放后半部分反转的值
    while(slow){
        
        temp=slow.next;
        slow.next=L;
        L=slow;
        slow=temp;
    }

    while(L && L.next){
        if(head.val!=L.val)
            return false;        
        head=head.next;
        L=L.next;
    }
    return true;
};
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

234. 回文链表
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。