回文链表Leetcode解决方案  


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple 彭博 Capital One公司 思科 Facebook 谷歌 英特尔 IXL 微软 Nutanix 神谕 Paytm Snapchat 尤伯杯 Yandex的
算法 编码 访谈 面试准备 力码 力码解决方案 链表 两个指针

在“ Palindrome链表”问题中,我们必须检查给定的整数是否 链表 是不是回文。

使用案列  

List = {1 -> 2 -> 3 -> 2 -> 1}
true

说明#1:列表为回文,因为从头到尾的所有元素的值都相同。

List = {1 -> 2 -> 3 -> 4 -> 5}
false

说明#2:该列表不是回文,因为来回的元素不相同。

方法(递归 

这很容易注意到,我们需要从阵列的背面获取节点的详细信息,以检查回文性质。 在这种情况下,我们有一个 单独地 链表意味着我们只能向前迭代才能到达任何节点。 因此,使用某种数据结构从背面固定节点就变得很重要,例如 堆 是一个可能的选项,因为它将最新节点保留在顶部。 我们也可以类似地使用递归。 递归是一种很好的方式,可以以相反的顺序获取节点值。 考虑下面的一般伪代码以更好地理解:

inorderTraversal(root)
{
    if(root == null)
        return;
    inorderTraversal(root.left);
    print(root.data);
    inorderTraversal(root.right);
}

上面的代码先打印 左 树中的节点,因为我们在打印节点本身的值之前递归地调用该函数以转到任何根的左子节点。 同样,我们可以使用 递归 首先转到最后一个节点,然后该函数回溯时,我们将以相反的顺序获取节点值。 我们将使用一个变量来迭代向前,该变量将不受递归的影响。 这样,我们可以比较通过递归获得的正向迭代器的值和反向节点的值,以比较元素。

参见
清除IP地址Leetcode解决方案

算法

  1. 功能 isPalindrome() 用于返回列表是否带有 头 是否回文
  2. 我们声明名为的类的数据成员 前 存储节点以进行正向迭代
  3. In isPalindrom():
    • 初始化 前=头
    • 返回palindromeCheck(头)
  4. In 回文检查当前):
    • If 当前 is :
      • 回报 true
    • If 回文检查当前) is false:
      • 回报 false
    • If 当前值 is 不是 等于 前值
      • 回报 false
    • 将前端递增为:
      • 前 = 前.下
    • 回报 true 当我们执行所有检查时
  5. 打印结果

回文链表Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

bool palindromeCheck(listNode* head)
{
    if(head == NULL)
        return true;
    if(!palindromeCheck(head->next))
        return false;
    if(front->value != head->value)
        return false;
    front = front->next;
    return true;
}

bool isPalindrome(listNode* head)
{
    front = head;
    return palindromeCheck(head);
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Java程序

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    static listNode front;
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static boolean palindromeCheck(listNode head)
    {
        if(head == null)
            return true;
        if(!palindromeCheck(head.next))
            return false;
        if(front.value != head.value)
            return false;
        front = front.next;
        return true;
    }

    static boolean isPalindrome(listNode head)
    {
        front = head;
        return palindromeCheck(head);
    }
}
true

回文链表Leetcode解决方案的复杂性分析

时间复杂度

上) 因为我们使用递归遍历了列表。 在这里,N =列表中的节点数。

参见
序列化和反序列化二叉树

空间复杂度

上) 当我们调用一个递归函数来检查创建的每个节点时 N 将帧堆叠在内存中。

进场(反向另一半)  

摆脱递归使用的空间的唯一方法是就地修改给定列表。 我们反转链表的后半部分,然后对两个半部使用两个正向迭代器,以检查对应的值是否相等。 对于此过程,我们需要:

  • 找到列表的中间位置,以便我们可以倒转下半部分。
  • 创建一个函数以反转列表的后半部分
  • 检查上半部分和下半部分是否相等

以上所有内容均可在线性时间内完成。 反向链接列表后,我们开始检查直到下半部分完成。

回文链表Leetcode解决方案

算法

  1. If is :
    • 返回true
  2. 使用找到链接列表的中间位置 middleOfList(功能:
    • 初始化两个指针 放慢 以及 快 都指向列表的开头
    • 直到 快速下一个 以及 快速下一个下一个 都是 不是 空值:
      1. 增量 放慢 到1年, 慢=慢。下一个
      2. 增量 到2年, 快速= fast.next.next
    • 放慢 指针现在指向列表的中间
    • 回报 放慢
  3. 现在我们反转列表调用的后半部分 reverseList(head = 中间.下一个) 功能
    • 初始化 上一页 =
    • 不为空:
      • 将下一个节点存储在一个临时变量中,如下所示 下页
      • 通过使用反转指针方向 head.next =上一个
      • 上一页=头
      • 使用以下方法在列表中前进 头=下一个
    • 回报 上一页
  4. 现在,初始化两个指针 ptr1 以及 ptr2 遍历这两个部分:
    1. ptr1 =头
    2. ptr2 =开始 下半场
    3. ptr2 不为空:
      1. if ptr1. 不等于 ptr2.
        1. 回报 false
    4. 回报 true 当我们检查上半年和下半年的每个节点时
  5. 打印结果
参见
K空槽LeetCode

回文链表Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* middleOfList(listNode* head)
{
    listNode *slow = head , *fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

listNode* reverseList(listNode* head)
{
    listNode *prev = NULL;
    while(head != NULL)
    {
        listNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(listNode* head)
{
    if(head == NULL)
        return true;
    listNode* middleNode = middleOfList(head);
    listNode* startOfSecondHalf = reverseList(middleNode->next);

    listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
    while(ptr2 != NULL)
    {
        if(ptr1->value != ptr2->value)
            return false;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return true;
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Java程序

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static listNode middleOfList(listNode head)
    {
        listNode slow = head , fast = head;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static listNode reverseList(listNode head)
    {
        listNode prev = null;
        while(head != null)
        {
            listNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(listNode head)
    {
        if(head == null)
            return true;
        listNode middleNode = middleOfList(head);
        listNode startOfSecondHalf = reverseList(middleNode.next);

        listNode ptr1 = head , ptr2 = startOfSecondHalf;
        while(ptr2 != null)
        {
            if(ptr1.value != ptr2.value)
                return false;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return true;
    }
}
true

回文链表Leetcode解决方案的复杂性分析

时间复杂度

上) 因为我们使用线性循环来找到列表的中间,将其反转,然后比较两个半部。 这里, N =列表的大小。

参见
将所有小于或等于k的元素组合在一起所需的最小交换

空间复杂度

O(1) 因为我们只使用恒定的额外空间。