LeetCode Hot 热题100 算法题 234.回文链表-算法&测试-easy模式

LeetCode Hot 热题100 算法题 234.回文链表-算法&测试-easy模式

请判断一个链表是否是回文链表。
输入1：1->2
输出：false
输入2：1->2->1
输出：true
你能否用O(n)时间复杂度和O(1)空间复杂度解决？

package leetcode.easy;

import java.util.ArrayList;
import java.util.List;

//234.回文链表：以链表中间检点为中心点 两边值对称
public class Solution234 {
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next=new ListNode(3);
		head.next.next=new ListNode(1);
		S234PalindromeList testPalindromeList = new S234PalindromeList();
		System.out.println(testPalindromeList.isPaliList(head));
	}
}

class S234PalindromeList{
	//法1：数组双指针 需要额外空间
	public boolean paliList(ListNode head) {
		//1.将链表的值复制到数组中
		ListNode cur = head;
		List<Integer> vals = new ArrayList<Integer>();
		while(cur!=null) {
			vals.add(cur.val);
			cur=cur.next;
		}
		//2.左指针从下标0开始，右指针从数组末尾开始，比较值是否相同，只要有不同就不是回文链表
		int left=0;
		int right=vals.size()-1;
		while(left<right) {
			if (!vals.get(left).equals(vals.get(right))) {
				return false;
			}
			left++;
			right--;
		}
		//3.while正常结束时 左右两侧对称，是回文链表
		return true;
	}
	
	//法2：快慢指针
	//1.找到链表前半部分的为节点（奇数个节点 中间节点算在前半部分）
	//2.反转后半部分链表（206.反转链表）
	//3.比较前半部分链表和反转的链表，判断是否回文
	//4.恢复后半部分链表
	//5.返回结果
	public boolean isPaliList(ListNode head) {
		//1.
		ListNode rightStart = startOfRight(head);
		//2.
		reverseList(rightStart);
		//3.
		boolean res = true;
		ListNode cur1=head;
		ListNode cur2=rightStart;
		while(cur2!=null) {
			if (cur1.val!=cur2.val) {
				res=false;
				break;
			}
			cur1=cur1.next;
			cur2=cur2.next;
		}
		//4.
		reverseList(rightStart);
		//5.
		return res;
	}
	//206.反转链表
	public ListNode reverseList(ListNode head) {
		ListNode rvsHead = null;
		ListNode next=null;
		ListNode cur = head;
		while(cur!=null) {
			next=cur.next;
			cur.next=rvsHead;
			rvsHead=cur;
			cur=next;
		}
		return rvsHead;
	}
	//找到中间节点
	public ListNode startOfRight(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;
		while(fast!=null && fast.next!=null) {
			fast=fast.next.next;
			slow=slow.next;
		}
		//若fast非空，说明有奇数个节点，slow正指向该中间节点，而后半部分不包含该节点，故将slow后移
		if (fast!=null) {
			slow=slow.next;
		}
		return slow;
	}
}

参考：

1. https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution
2. https://leetcode-cn.com/problems/palindrome-linked-list/solution/di-gui-zhan-deng-3chong-jie-jue-fang-shi-zui-hao-d