Leetcode.234 判断回文链表(双指针/快慢指针)

 这是力扣上的一道题，题目链接：https://leetcode.cn/problems/palindrome-linked-list/

目录

题目描述

解析

1、双指针

C++代码

C#代码

2、快慢指针

C++代码

C#代码

---

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

解析

这里给出两种解法：双指针法和快慢指针法。

1、双指针

        思路是把链表复制到另一个容器中，比如vector，然后用两个指针分别从容器头尾向中间遍历，遍历的过程中判断分别遍历到的结点是否相等即可。复制链表需要O(n)的时间，判断链表是否回文需要O(n/2)次判断，因此总时间复杂度为O(n) + O(n/2) = O(n)；由于将链表的n个结点全部复制到新的一个容器，因此空间复杂度为O(n)。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
       if(head == NULL) return false;
       vector<int> v;
       ListNode* p = head;
       while(p != NULL){
           v.emplace_back(p->val);
           p = p->next;
       }
       for(int i = 0, j = v.size() - 1; i < j; i++, j--)
           if(v[i] != v[j]) return false;
       return true;
    }
};

C#代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        if(head == null) return false;
        List<int> list = new List<int>();
        ListNode p = head;
        while(p != null){
            list.Add(p.val);
            p = p.next;
        }
        for(int i = 0, j = list.Count() - 1; i < j; i++, j--)
            if(list[i] != list[j]) return false;
        return true;
    }
}

2、快慢指针

        使用快慢指针，可以减少空间复杂度。思路是使用一个快指针和一个慢指针，每次循环，快指针移动两个结点，慢指针移动一个结点，这样当快指针移动到链表尾时，慢指针正好移动到链表中部(如果结点是奇数，则将多出来的一个结点也算入前一半链表中)，这样就把链表分成了两半。接下来把另一半链表反转，并与原来的一半链表进行对比，比较是否相等即可判断整个链表是否回文。整个操作概括步骤如下：

• 找到前半部分链表的尾节点。
• 反转后半部分链表。
• 判断是否回文。
• 返回结果。

时间复杂度总共为O(n)，n是指链表的大小。由于我们只会修改原本链表中结点的指向，而在堆栈上的堆栈帧不超过 O(1)，因此总的空间复杂度是O(1)。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL) return true;
        ListNode* firstHalfEnd = getHalf(head);  //得到前一半链表的尾结点
        ListNode* secondHalf = reverseList(firstHalfEnd->next); //将后一半链表反转
    
        //判断链表是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalf;
        while(p2 != NULL){    //当p2到达尾结点后终止循环，这样可以照顾到链表结点为奇数的情况
            if(p1->val != p2->val) return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }

    //得到前一半部分链表的尾结点
    ListNode* getHalf(ListNode* head){
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != NULL and fast->next->next != NULL){ //注意and两边条件的位置，交换会报错
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    //反转后一半链表(这里使用头插法建立反转后的链表)
    ListNode* reverseList(ListNode* head){
        ListNode* node = NULL;
        ListNode* newHead = NULL;
        ListNode* curr = head;
        while(curr != NULL){
            node = curr;
            curr = curr->next;
            node->next = newHead;
            newHead = node;
        }      
        return newHead;
    }
};

C#代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode firstHalfEnd = GetHalf(head);
        ListNode secondHalf = ReverseList(firstHalfEnd.next);

        ListNode p1 = head;
        ListNode p2 = secondHalf;
        while(p2 != null){
            if(p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    ListNode GetHalf(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    ListNode ReverseList(ListNode head){
        ListNode node = null;
        ListNode newHead = null;
        ListNode curr = head;
        while(curr != null){
            node = curr;
            curr = curr.next;
            node.next = newHead;
            newHead = node;
        }
        return newHead;
    }

}