问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3905 访问。
请判断一个链表是否为回文链表。
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3905 访问。
public class Program {
public static void Main(string[] args) {
var head = new ListNode(1) {
next = new ListNode(2) {
next = new ListNode(3) {
next = new ListNode(2) {
next = new ListNode(1)
}
}
}
};
var res = IsPalindrome(head);
Console.WriteLine(res);
res = IsPalindrome2(head);
Console.WriteLine(res);
Console.ReadKey();
}
private static bool IsPalindrome(ListNode head) {
var list = new List<int>();
var node = head;
while(node != null) {
list.Add(node.val);
node = node.next;
}
var mid = list.Count / 2;
for(var i = 0; i < mid; i++) {
if(list[i] != list[list.Count - i - 1]) return false;
}
return true;
}
private static bool IsPalindrome2(ListNode head) {
var list = new List<int>();
var list2 = new List<int>();
var node = head;
while(node != null) {
list.Add(node.val);
list2.Add(node.val);
node = node.next;
}
list.Reverse();
for(var i = 0; i < list.Count; i++) {
if(list[i] != list2[i]) return false;
}
return true;
}
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3905 访问。
True
True分析：
显而易见，以上2种算法的时间复杂度均为： 。