Palindrome List

发表于 | 分类于

Palindrome List(判断链表是否是回文链表)

题目描述：

给定一个链表的头结点，判断链表是否是回文结构。

例子：

1->2->3->2->1->NULL即为回文链表

解题思路1：

回文的结构的特点是正序和逆序的访问结果是一致的。所以第一种想法是利用栈结构来逆序链表。首先申请一个栈空间，然后遍历链表，将链表中的数据不断的压栈。然后再次遍历链表和栈，如果出现栈中的数据和链表中的数据不一致的情况即为非回文结构。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class isPalindrome1{
public:
    bool isPalindrome(ListNode* head){
        stack<int> stk; // 申请栈空间
        ListNode* temp = head;
        while(temp != NULL){
            stk.push(temp->val);
            temp = temp->next;
        }             //数据压栈
        while(head != NULL){
            if (stk.top() != head->val) {
                return false;
            }          
            else{
                stk.pop();
                head = head->next;
            }
        }        //判断元素是否相同
        return true;
    }
};

解题思路2:

在原先的基础上我们可以通过找到链表的中间节点，然后用先前的栈的一半空间即可实现。主要想法是我们可以找到例子中的中间节点3；然后我们可以将后半部分2->1->NULL压栈；然后从链表头部和栈顶开始遍历数据判断是否相等即可。

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
class isPalindrome2{
public:
    bool isPalindrome(ListNode* head){
        ListNode* cur = head;
        ListNode* right = head->next;
        if (head == nullptr || right == NULL)
            return false;
        while(cur->next != nullptr && cur->next->next != NULL){
            right = right->next;
            cur = cur->next->next;
        }//找到中间节点
        stack<int> stk;
        while(right != NULL){
            stk.push(right->val);
            right = right->next;
        } //压栈
        while(!stk.empty()){
            if (stk.top() != head->val)
                return false;
            else{
                stk.pop();
                head = head->next;
            }
        }//判断是否相等
        return true;
    }
};

解题思路3:

判断回文的过程中，我们遇到的另外一个问题是对于链表我们无法逆序查找，如果可以的话我们就可以直接从链表的头部和尾部同时查找然后判断是否是回文即可。所以基于这个思路，我们可以将链表的后半段改变指针的指向后，然后从左右侧同时开始遍历判断是否相等即可。

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
class Solution3 {
public:
    bool isPalindrome3(ListNode* head) {
        if (head->next == NULL || head->next->next == NULL)
            return true;
        ListNode* n1 = head;
        ListNode* n2 = head;
        while(n2->next != NULL && n2->next->next != NULL){
            n1 = n1->next;
            n2 = n2->next->next;
        }             //快慢指针找到链表的中部节点
        n2 = n1->next;
        n1->next = NULL;
        ListNode* n3 = NULL;
        while(n2 != NULL){
            n3 = n2->next;
            n2->next = n1;
            n1 = n2;
            n2 = n3;
        }           //逆序后半部分链表
        n3 = n1;
        n2 = head;
        while(n1 != NULL && n2 != NULL){
            if(n1->val != n2->val){
                return false;
            }
            else{
                n1 = n1->next;
                n2 = n2->next;
            }
        } // 从左右侧同时遍历链表判断值是否相等
        return true;
    }
};