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

示例 1:

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

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？（leetcode原题）

拿到这个题的时候，看到给出的第二个示例以及要求O(1) 空间复杂度就知道要利用链表逆序思想，将链表后半部分逆序。然后从前到中和从后到中一一对比即可。

实现代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
    if(head==NULL || head->next == NULL){
      return true;  
    }
        
    bool result = true;
    struct ListNode* node1 = head;
    struct ListNode* node2 = head;
    struct ListNode* node3 = NULL;
    
    //node2每次跳两步，node1每次跳一步，当node2->next或者node2->next->next为空时
    //链表个数为奇数，node1就处在中间位置，
    //链表个数为偶数，node1和node1->next就是中间两个位置。
    while(node2->next!=NULL && node2->next->next !=NULL){
        node2 = node2->next->next;
        node1 = node1->next;
    }
    
    //逆序后半段链表
    // 1->2->3->3->2->1
    //     转为
    // 1->2->3<-3<-2<-1
    node2 = node1->next;
    node1-> next = NULL;
    while(node2!=NULL){
        node3 = node2->next;
        node2->next = node1;
        node1 = node2;
        node2 = node3;
    }
    
    node3 = node1;
    node2 = head;
    
    //从前端和后端开始对比数字
    while(node2!=NULL && node1!=NULL){
        if(node2->val != node1->val){
            result = false;
            break;
        }
        node2 = node2->next;
        node1 = node1->next;
    }
    
    //在程序中应该把链表恢复原样，毕竟还有可能要用到这个链表，参照上面，这里就偷懒没写了
    
    return result;
}

好久没有写算法了，为了链表的逆序在纸上画了半天才理清逻辑。。。