C# 判断字符串是否是回文字符串(单链表)

回文字符串：

ABCDCBA

ABCDDCBA

两种都属于回文字符串；

如何判断一个字符串是否是否回文：

• 使用快慢指针，判断出中间节点(慢指针每次前进一步，快指针每次前进两步)；
• 将慢指针进行反转；
• 前后半部分比较，判断是否为回文

时间复杂度：O(n)

空间复杂度：O(1)

空间复杂度要看额外的内存消耗，不是看链表本身存储需要多少空间。

 public static void IsPlalindrome()
        {
            LinkedList<int> ll = new LinkedList<int>();
            ll.Insert(1);
            ll.Insert(2);
            ll.Insert(3);
            ll.Insert(4);
            ll.Insert(3);
            ll.Insert(2);
            ll.Insert(1);

            Node<int> pre = null;

            Node<int> next = null;
            Node<int> fast = ll.Head;
            Node<int> slow = ll.Head;

            while (fast != null && fast.Next != null)
            {
                fast = fast.Next.Next;
                next = slow.Next;
                slow.Next = pre;
                pre = slow;
                slow = next;
            }

            if (fast != null)//当字符串未基数数 Slow为中间节点4，slow已经反转
            {
                slow = slow.Next;
            }

            while (slow != null) {
                if (slow.Data != pre.Data)
                {
                    Console.WriteLine("非回文");
                    return;
                }

                pre = pre.Next;
                slow = slow.Next;
            }

            Console.WriteLine("回文");
            Console.ReadLine();
        }