Leetcode: 【每日一题】- 2019-10-17 - 234. 回文链表

[azl397985856]

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

示例 1:

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

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

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

[azl397985856]

#
# @lc app=leetcode.cn id=234 lang=python3
#
# [234] 回文链表
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        pre = None
        slow = fast = head

        # 一边反转前半部分，一边找中点
        while(fast and fast.next):
            # 先更新fast指针
            fast = fast.next.next
            # 再反转和更新slow指针
            next = slow.next
            slow.next = pre
            pre = slow
            slow = next
        # 处理奇数个节点的情况
        if fast:
            slow = slow.next
        # 从中点开始分别向前和后遍历，逐个比较是否相同即可
        while(slow):
            if (slow.val != pre.val):
                return False
            pre = pre.next
            slow = slow.next
        return True

        # @lc code=end

[watchpoints]

c++版本
~~~
**

• Definition for singly-linked list.
• struct ListNode {
• int val;
• ListNode *next;
• ListNode(int x) : val(x), next(NULL) {}
• };
  /
  /*
  1 定义2个指针，head tail
  
  
  
  1. 递归遍历tail链表
  
  
  2. 通过
     
     head++ 链表前进, 递归特点:从上到下
     
     这个是子递归完在函数内部修改的，然后当前递归在使用
     
     head已经发生改变）
     
     tail -- 链表倒退,
     
     递归特点 回溯，利用函数栈跟踪轨获取最后节点。
     
     tail没有改变
     
     判断是否回文 tail ==head
     
     4.如果是继续，如果不是返回false
     
     */
     
     class Solution {
     
     public:
     
     bool isPalindrome(ListNode head) {
  
  

    return isPalindrome(head,head);
}
//bool isPalindrome(ListNode* tail,ListNode* head)
bool isPalindrome(ListNode* tail,ListNode* &head)
{
    if(NULL==tail) 
    {
        return true;
    }

    bool flag=isPalindrome(tail->next,head);
    if (false ==flag)
    {
        return false;

    }

    if (tail->val !=head->val)
    {
        return false;
    }
    head =head->next;//
    return flag;

}

};
~~~

[maninbule]

领取

使用递归的回溯来逆序访问链表，然后逆序过程中和正序进行比较就。没有出现不等的情况就是回文

class Solution {
public:
    ListNode *h;
    bool ok = true;
    bool isPalindrome(ListNode* head) {
        h = head;
        DFS(head);
        return ok;
    }

    void DFS(ListNode* tail){
        if(tail == NULL) return ;
        else{
            DFS(tail->next);
            if(tail->val != h->val) ok = false;
            h = h->next;
        }
    }
};

[azl397985856]

领取

使用递归的回溯来逆序访问链表，然后逆序过程中和正序进行比较就。没有出现不等的情况就是回文

class Solution {
public:
    ListNode *h;
    bool ok = true;
    bool isPalindrome(ListNode* head) {
        h = head;
        DFS(head);
        return ok;
    }

    void DFS(ListNode* tail){
        if(tail == NULL) return ;
        else{
            DFS(tail->next);
            if(tail->val != h->val) ok = false;
            h = h->next;
        }
    }
};

done，但是其他解答把我的加上，因为你的空间复杂度不是常数

[wangyuxiang0829]

O(n)时间复杂度 O(1)空间复杂度 三指针 c++实现

#include <cassert>
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool isPalindrome(ListNode *head) {
        if (!head || !head->next) return true;
        ListNode *left = head, *right = head, *pre = nullptr;
        while (right && right->next) {
            right = right->next->next;
            auto tmp = left->next;
            left->next = pre;
            pre  = left;
            left = tmp;
        }
        if (right) left = left->next;
        while (left) {
            if (pre->val != left->val) return false;
            pre  = pre->next;
            left = left->next;
        }
        return true;
    }
};

int main() {
    ListNode node1(1);
    ListNode node2(2);
    node1.next = &node2;
    assert(Solution().isPalindrome(&node1) == false);
}

[aaaaaabiao]

java解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode s1 = head;
        ListNode s2 = slow;
        //说明奇数个数
        if(fast != null) {
            s2 = s2.next;
        }


        //将s2反转
        ListNode p = s2;
        s2 = null;
        while(p != null) {
            ListNode next = p.next;
            p.next = s2;
            s2 = p;
            p = next;
        }

        while(s2 != null) {
            if(s1.val != s2.val) {
                return false;
            }

            s2 = s2.next;
            s1 = s1.next;
        }

        return true;

    }
}