[LeetCode] 234. Palindrome Linked List

轉自LeetCode

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?

<Solution>

解提想法如下

• 利用快慢指標來找到中間點

• 把後半部反轉

• 逐一檢查前半部和後半部的元素，是否都相同

code 如下

C++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isPalindrome(ListNode* head) {
	if(!head || !head->next) {
	return true;
	}
	ListNode *fast = head;
	ListNode *slow = head;
	//>> find the mid point
	while(fast->next && fast->next->next) {
	fast = fast->next->next;
	slow = slow->next;
	}
	//>> reverse the second half
	slow->next = reverse(slow->next);
	slow = slow->next;
	while(slow) {
	if(head->val != slow->val) {
	return false;
	}
	head = head->next;
	slow = slow->next;
	}
	return true;
	}
	ListNode *reverse(ListNode *head) {
	ListNode *newHead = NULL;
	ListNode *nextHead;
	while(head) {
	nextHead = head->next;
	head->next = newHead;
	newHead = head;
	head = nextHead;
	}
	return newHead;
	}
	};

view raw palindromeLinkedList.cpp hosted with ❤ by GitHub

Java

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public boolean isPalindrome(ListNode head) {
	if(head == null || head.next == null) {
	return true;
	}
	ListNode slow = head;
	ListNode fast = head;
	//>> find mid point
	while(fast.next != null && fast.next.next != null) {
	slow = slow.next;
	fast = fast.next.next;
	}
	//>> reverse second half
	slow.next = reverse(slow.next);
	slow = slow.next;
	while(slow != null) {
	if(head.val != slow.val) {
	return false;
	}
	head = head.next;
	slow = slow.next;
	}
	return true;
	}
	private ListNode reverse(ListNode head) {
	ListNode newHead = null;
	ListNode nextHead;
	while(head != null) {
	nextHead = head.next;
	head.next = newHead;
	newHead = head;
	head = nextHead;
	}
	return newHead;
	}
	}

view raw palindromeLinkedList.java hosted with ❤ by GitHub

還有一種解法，可以借用 stack

先把 node 都放到 stack 裡面，然後只要拿出後半部，逐一比對即可

因為 stack 是 FILO 的結構，所以剛好會用反過來的順序拿出 node

kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun isPalindrome(head: ListNode?): Boolean {
	val stack = mutableListOf<ListNode>()
	var curr = head
	while(curr != null) {
	stack.add(curr!!)
	curr = curr?.next
	}
	var limit = stack.size / 2
	curr = head
	while (limit > 0) {
	if(curr!!.`val` != stack.last().`val`) {
	return false
	}
	curr = curr!!.next
	stack.removeAt(stack.lastIndex)
	--limit
	}
	return true
	}
	}

view raw palindrome_linked_list.kt hosted with ❤ by GitHub