JavaScript判斷單連結清單是否為回文結構的多種方法

一、什麼是回文結構？

回文結構就是類似于ABBA、ABA、A的形式

示例1：a -> b -> c -> c - >b - >a

示例2：a -> b -> a

示例3：a

示例4：abccba

二、回文結構判斷方法

1.字元串類型

将字元串轉換成數組之後，反轉數組，然後将數組 的内容拼接轉換成字元串，與源字元串比對

let str = 'abccba'
function isPalindrome(str){
	if(str.length === 1){
		return true
	}else{
		let reverseStr = Array.from(str).reverse().join(' ');
		if(reverseStr == str){
			return true;
		}else{
			return false;
		}
	}
}
           

2.連結清單類型

1. 使用棧的方式，周遊單連結清單，将連結清單中的每個節點添加到數組中，然後再次周遊連結清單，同時對數組進行彈棧操作，依次比對。因為棧是後進先出，是以是按照連結清單的最後一個節點開始彈棧

function isPalindrome = function(head) {
	if(head === null || head.next === null){
		return true
	}
	// 1.使用棧的方式
	let current = head;
	let stack = new Array();
	// 周遊連結清單，入棧
	while (current != null) {
		stack.push(current);
		current = current.next;
	}
	// 再次周遊連結清單，彈棧判斷
	current = head;
	while (current != null) {
		if (current.val !== stack.pop().val) {
			return false
		}
		current = current.next;
	}
	return true
}
           

2.使用字元串反轉判斷(暴力解決)，周遊一次單連結清單後，我們可以将連結清單中的字元串提取出來，拼接成一個字元串，然後使用字元反轉進行回文判斷

function isPalindrome = function(head){
	// 2.使用字元串反轉判斷
	if (head === null || head.next === null) {
		return true
	}
	let str = '',
		current = head;
	//周遊連結清單，拼接字元串
	while(current !== null){
		str += current.val;
		current = current.next;
	}
	if(str === Array.from(str).reverse().join('')){
		return true
	}else{
		return false
	}
}
           

3.使用快慢指針，空間複雜度為O(1)，定義兩個指針（fast、slow），周遊連結清單，慢指針slow每次移動一步，fast每次移動兩步。當周遊結束之後，慢指針正好指向連結清單的中間，然後從該節點開始對後半部分連結清單進行反轉。然後再次周遊，依次比對

function isPalindrome = function(head) {
	if (head === null || head.next === null) {
		return true
	}
	// 3.使用快慢指針
	let fast = head,
		slow = head,
		current = head;
	// 周遊連結清單，移動快慢指針
	while (fast.next !== null && fast.next.next !== null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	// 此時當快指針移動到末端時，慢指針移動到中間，反轉慢指針之後的連結清單
	let reverseListHead = reverseList(slow);
	// 周遊連結清單,判斷兩個連結清單是否相等
	while (current !== null && reverseListHead !== null) {
		if (current.val !== reverseListHead.val) {
			return false
		}
		current = current.next;
		reverseListHead = reverseListHead.next;
	}
	return true;
}
//反轉連結清單
function reverseList(current) {
	let pre = null,
		curr = current;
	while (curr != null) {
		let nextNode = curr.next;
		curr.next = pre;
		pre = curr;
		curr = nextNode;
	}
	return pre;
}
           

總結

判斷連結清單是否回文是面試中的常考題，主要的思想就是對連結清單進行反轉，周遊比對。使用快慢指針可以使得空間複雜度為O(1)，不需要額外使用其他類似數組等資料結構，對于字元串的回文可以将它轉換成數組，然後進行反轉比對。