【算法积累】回文链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法积累】回文链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1928字，纯文字阅读大概需要3分钟。

内容图文

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?快慢指针
我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。
语言：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官方题解指出，比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。在上面的代码中我并没有恢复链表结构，只是可以达到解题的效果。

内容总结

以上是互联网集市为您收集整理的【算法积累】回文链表全部内容，希望文章能够帮你解决【算法积累】回文链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---