一【题目类别】

链表

二【题目难度】

简单

三【题目编号】

234.回文链表

四【题目描述】

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

五【题目示例】

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

六【题目提示】

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

七【题目进阶】

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

八【解题思路】

如果用栈或者数组做这个题很简单，没有什么难度，但是题目进阶说了要保证 O ( 1 ) O(1) O(1)的时间复杂度，也就是说不能开辟新的内存空间。那么我们可以利用快慢指针的思想来保证题目要求的时间复杂度。具体思路如下： ①：首先用快慢指针找到链表中点 ②：然后将链表后半段反转 ③：最后逐一对比两个链表即可，如果有不同的就不是回文链表，否则就是回文链表

九【时间频度】

时间复杂度： O ( n ) O(n) O(n)，其中 n n n为链表长度 空间复杂度： O ( 1 ) O(1) O(1)

十【代码实现】

1. Java语言版

package LinkedList;

public class p234_PalindromicLinkedList {
          
   

    int val;
    p234_PalindromicLinkedList next;

    public p234_PalindromicLinkedList() {
          
   
    }

    public p234_PalindromicLinkedList(int val) {
          
   
        this.val = val;
    }

    public p234_PalindromicLinkedList(int val, p234_PalindromicLinkedList next) {
          
   
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
          
   
        p234_PalindromicLinkedList node1 = new p234_PalindromicLinkedList(1);
        p234_PalindromicLinkedList node2 = new p234_PalindromicLinkedList(2);
        p234_PalindromicLinkedList node3 = new p234_PalindromicLinkedList(2);
        p234_PalindromicLinkedList node4 = new p234_PalindromicLinkedList(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        boolean res = isPalindrome(node1);
        System.out.println(res);
    }

    public static boolean isPalindrome(p234_PalindromicLinkedList head) {
          
   
        p234_PalindromicLinkedList slow = head, fast = head, pre = null, temp = null;
        while (fast != null) {
          
   
            slow = slow.next;
            fast = fast.next != null ? fast.next.next : fast.next;
        }
        while (slow != null) {
          
   
            temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        while (head != null && pre != null) {
          
   
            if (head.val != pre.val) {
          
   
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }

}

2. C语言版

#include<stdio.h>
#include<stdbool.h>

struct ListNode
{
          
   
	int val;
	struct ListNode *next;
};

bool p234_PalindromicLinkedList_isPalindrome(struct ListNode* head)
{
          
   
	struct ListNode *slow = head, *fast = head, *pre = NULL, *temp = NULL;
	while (fast != NULL)
	{
          
   
		slow = slow->next;
		fast = fast->next ? fast->next->next : fast->next;
	}
	while (slow != NULL)
	{
          
   
		temp = slow->next;
		slow->next = pre;
		pre = slow;
		slow = temp;
	}
	while (head != NULL && pre != NULL)
	{
          
   
		if (head->val != pre->val)
		{
          
   
			return false;
		}
		head = head->next;
		pre = pre->next;
	}
	return true;
}

/*主函数省略*/

十一【提交结果】

1. Java语言版
2. C语言版