力扣234题回文链表(java对撞双指针法，快慢指针法)

题目描述:

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解题思路 + 代码:

思路1：对撞双指针法： 对于最常见的题目就是判断一个串是否为回文字符串，此时由于字符串的底层是字符数组，我们容易想到用对撞双指针进行判断（一个指针指向数组头，一个指向数组尾部，循环向数组中间“靠拢”并比较每队字符是否相等）对于此题目我们也很容易想到此方法，但是由于此题目是用单链表来储存字符，我们无法从链表的尾部操作指针向前移动，所以我们就想到先依次将节点的数值域依次取出存入一个数组中（我们使用java支持动态扩容的容器ArrayList）再使用之前的常用操作。

public boolean isPalindrome(ListNode head) {
          
   
	//Time Complexity: O(N)	
	//Space Complexity: O(N)
	ArrayList<Integer> list = new ArrayList<>();
	ListNode cur = head;
	while (cur != null) {
          
   
		//添加链表的数值域
		list.add(cur.val);
	}
	//定义左右指针
	int left = 0;
	int right = list.size() - 1;
	while (left < right) {
          
   
		if (!(list.get(left).equals(list.get(right))) ) {
          
   
			return false;
		}	
	}
	return true;
}

思路2：快慢指针法： 我们可以定义一个快指针和慢指针，让慢指针每次移动一个节点，快指针每次移动两个节点，我们易发现，当链表长度为奇数时，当快指针位于链表尾部时此时慢指针位于中间的节点，此时我们将慢指针再后移一位后将此时的慢指针和其后面的节点反转（对于单链表的反转可以看力扣206题），再让快指针重新指向表头，再让此时的快慢指针每次移动一步，依次比较节点的数值域；对于链表长度为偶数情况，我们容易发现只需要省去当快指针位于链表尾部时，再将慢指针向后移动一位的操作

思路2图示:

public boolean isPalindrome(ListNode head) {
          
   
	//Time Complexity: O(N)
	//Space Complexity: O(1)
	
	//定义快慢指针
	ListNode fast = head;
	ListNode slow = head;
	while (fast != null && fast.next != null) {
          
   
		fast = fast.next.next;
		slow = slow.next;
	}
	
	//当链表长度为奇数
	//此时若fast不指向null则长度为奇数
	if (fast != null) {
          
   
		slow = slow.next;
	}
	slow = reverse(slow);
	//将快指针重新指向表头
	fast = head;
	while (slow != null) {
          
   
		if (fast.val != slow.val) {
          
   
			return false;
		}
		slow = slow.next;
		fast = fast.next;
	}
	return true;
}
//辅助函数，反转链表
private ListNode reverse(ListNode head) {
          
   
	ListNode pre = null;
	ListNode cur = head;
	while (cur != null) {
          
   
		ListNode next = cur.next;
		cur.next = pre;
		pre = cur;
		cur = next;
	}
	return pre;
}

部分分析：

对于代码1，在力扣的控制台上会执行超时，但是用大O分析法其时间复杂度是为O(N)的，个人认为原因是每次在使用ArrayList动态扩容时（ArrayList的扩容效率低）会花费额外的时间以至于超时。