【算法积累】回文链表

雨点打透心脏的1/2处 2022-12-23 07:12 97阅读 0赞

## LeetCode 234. 回文链表 ##

**难度** 简单

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

**示例1**

输入: 1->2
    输出: false

**示例2**

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

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

--------------------

**解法1** 数组+双指针  
复制链表值到数组列表中，然后使用双指针法判断是否为回文。  
语言：C

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    
    bool isPalindrome(struct ListNode* head) { 
        int nums[50000];
        int len = 0;
        while (head) { 
            nums[len++] = head->val;
            head = head->next;
        }
        for (int i = 0, j = len - 1; i < j; i++, j--) { 
            if (nums[i] != nums[j]) { 
                return false;
            }
        }
        return true;
    }

时间复杂度： O ( n ) O(n) O(n)  
空间复杂度： O ( n ) O(n) O(n)

--------------------

**解法2** 快慢指针+栈  
语言：Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isPalindrome(ListNode head) { 
            if (head == null) { 
                return true;
            }
            if (head.next == null) { 
                return true;
            }
            if (head.next.next == null) { 
                return head.val == head.next.val;
            }
            ListNode slow = head;
            ListNode fast = head;
            Stack<Integer> stack = new Stack<>();
            while (fast.next != null && fast.next.next != null) { 
                fast = fast.next.next;
                stack.push(slow.val);
                slow = slow.next;
            }
            if (fast.next != null && fast.next.next == null) { 
                // 链表长度为偶数
                stack.push(slow.val);
            }
            slow = slow.next;
            while (!stack.isEmpty()) { 
                if (slow.val != stack.pop())
                    return false;
                slow = slow.next;
            }
            return true;
        }
    }

时间复杂度： O ( n ) O(n) O(n)  
空间复杂度： O ( n ) O(n) O(n)

--------------------

**解法3** 快慢指针+链表反转  
我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。  
语言：C

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    
    struct ListNode* reverse(struct ListNode* head) { 
        /** * reverse()用于反转单链表 */
        struct ListNode* pre = NULL;
        struct ListNode* cur = head;
        while (cur) { 
            struct ListNode* nextNode = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nextNode;
        }
        return pre;
    }
    
    struct ListNode* endOfFirstHalf(struct ListNode* head) { 
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while (fast->next && fast->next->next) { 
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    
    bool isPalindrome(struct ListNode* head) { 
        if (head == NULL) { 
            return true;
        }
        struct ListNode* firstHalfEnd = endOfFirstHalf(head);
        struct ListNode* secondHalfStart = reverse(firstHalfEnd->next);
        struct ListNode* p1 = head;
        struct ListNode* p2 = secondHalfStart;
        bool ret = true;
        while (ret && p2) { 
            if (p1->val != p2->val) { 
                ret = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return ret;
    }

时间复杂度： O ( n ) O(n) O(n)  
空间复杂度： O ( 1 ) O(1) O(1)  
注：LeetCode官方题解指出，比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。在上面的代码中我并没有恢复链表结构，只是可以达到解题的效果。

--------------------

**解法4** 哈希  
哈希公式：`hash = hash * seed + val`，其中`seed`是一个质数，`val`是节点的值。  
那么，顺序哈希的结果为 h a s h 1 = a \[ 1 \] × s e e d n − 1 + a \[ 2 \] × s e e d n − 2 + . . . + a \[ n − 1 \] × s e e d 1 + a \[ n \] × s e e d 0 . hash1=a\[1\]×seed^\{n-1\}+a\[2\]×seed^\{n-2\}+...+a\[n-1\]×seed^1+a\[n\]×seed^0. hash1=a\[1\]×seedn−1\+a\[2\]×seedn−2\+...\+a\[n−1\]×seed1\+a\[n\]×seed0.逆序哈希的结果为 h a s h 2 = a \[ 1 \] × s e e d 0 + a \[ 2 \] × s e e d 1 + . . . + a \[ n − 1 \] × s e e d n − 2 + a \[ n \] × s e e d n − 1 . hash2=a\[1\]×seed^0+a\[2\]×seed^1+...+a\[n-1\]×seed^\{n-2\}+a\[n\]×seed^\{n-1\}. hash2=a\[1\]×seed0\+a\[2\]×seed1\+...\+a\[n−1\]×seedn−2\+a\[n\]×seedn−1.  
我们发现，逆序哈希的结果也能正序计算得出，最后比较`hash1 == hash2`即可。  
语言：Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isPalindrome(ListNode head) { 
            long hash1 = 0;
            long hash2 = 0;
            long h = 1;
            long seed = 3;
            while (head != null) { 
                hash1 = hash1 * seed + head.val;
                hash2 = hash2 + h * head.val;
                h *= seed;
                head = head.next;
            }
            return hash1 == hash2;
        }
    }

时间复杂度： O ( n ) O(n) O(n)  
空间复杂度： O ( 1 ) O(1) O(1)