234. 回文链表

Problem: 234. 回文链表

解题方法

方法一:

• 将链表赋值为数组

    - 前后指针

    - 开始遍历 当前指针小于后指针

    - 当前后不相等时

        - return false

    - 遍历结束

    - return true  

注意当长度为1时也是回文串。

方法二:

• 找到中间节点和尾部节点

• 从中间节点开始翻转尾部节点

• 翻转过后再开始分别从头部和中间节点遍历

    - 如果 前 != 后

        - 从中间节点再翻转回来  

        - return false

• 遍历结束

• 从中间节点再翻转回来

• return true

         

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

法1:

class Solution {

public:

    bool isPalindrome(ListNode* head) {

        vector<int> help;

        ListNode* cur = head;

        while (cur != nullptr) {

            help.push_back(cur->val);

            cur = cur->next;

        }

        if(help.size() == 1) return true;

        int i = 0,j = help.size() - 1;

        while (i <= j) {

            if (help[i] != help[j])

                return false;

            i++;

            j--;

        }

        return true;

    }

};

法2:

public class Solution {

    public bool IsPalindrome(ListNode head) {

        List<int> arr = new List<int>();

  

       ListNode currentNode = head;

        while (currentNode != null) {

            arr.Add(currentNode.val);

            currentNode = currentNode.next;

        }

  

        int front = 0;

        int back = arr.Count -1;

        while(front < back) {

            if(arr[front] != arr[back]) {

                return false;

            }

            front++;

            back--;

        }

        return true;

    }

}