LeetCode - Easy - 234. Palindrome Linked List

缺乏、安全感 2023-01-02 13:25 170阅读 0赞

## Topic ##

*  Linked List
 *  Two Pointers

## Description ##

[https://leetcode.com/problems/palindrome-linked-list/][https_leetcode.com_problems_palindrome-linked-list]

Given a singly linked list, determine if it is a palindrome.

**Example 1**:

Input: 1->2
    Output: false

**Example 2**:

Input: 1->2->2->1
    Output: true

**Follow up**:  
Could you do it in O(n) time and O(1) space?

## Analysis ##

方法一：我写的，双指针。由于是单向链表而不是双向链表，其中一指针要反复横跳。时杂O(N²)，空杂O(1)。

方法二：使用栈。时杂O(N)，空杂O(N)。

方法三：递归。时杂O(N)，空杂O(N)。

方法四：双指针，反转链表的半部分，这会修改原链表结构。时杂O(N)，空杂O(1)。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class PalindromeLinkedList { 
    
    	// 方法一：我写的
    	public boolean isPalindrome1(ListNode head) { 
    		if (head == null)
    			return false;
    
    		ListNode p1 = head, p2 = head;
    		int count = 0;
    
    		while (p1 != null) { 
    			p1 = p1.next;
    			count++;
    		}
    
    		int half = count - count / 2;
    
    		while (half-- > 0) { 
    			p2 = p2.next;
    		}
    
    		p1 = head;
    		for (int i = count / 2; i > 0; i--) { 
    			int step = i - 1;
    			while (step-- > 0) { 
    				p1 = p1.next;
    			}
    
    			if (p1.val != p2.val) { 
    				return false;
    			}
    			p1 = head;
    			p2 = p2.next;
    		}
    
    		return true;
    	}
    
    	// 方法二：使用栈
    	public boolean isPalindrome2(ListNode head) { 
    		ListNode temp = head;
    		LinkedList<Integer> stack = new LinkedList<>();
    		while (temp != null) { 
    			stack.push(temp.val);
    			temp = temp.next;
    		}
    
    		while (head != null) { 
    			if (head.val != (int) stack.pop()) { 
    				return false;
    			}
    			head = head.next;
    		}
    		return true;
    	}
    
    	// 方法三：递归
    	ListNode ref;
    
    	public boolean isPalindrome3(ListNode head) { 
    		ref = head;
    		return check(head);
    	}
    
    	public boolean check(ListNode node) { 
    		if (node == null)
    			return true;
    		boolean ans = check(node.next);
    		boolean isEqual = (ref.val == node.val) ? true : false;
    		ref = ref.next;
    		return ans && isEqual;
    	}
    
    	// 方法四：双指针，以及要反转链表
    	public boolean isPalindrome4(ListNode head) { 
    		ListNode fast = head, slow = head;
    		while (fast != null && fast.next != null) { 
    			fast = fast.next.next;
    			slow = slow.next;
    		}
    		if (fast != null) {  // odd nodes: let right half smaller
    			slow = slow.next;
    		}
    		slow = reverse(slow);
    		fast = head;
    
    		while (slow != null) { 
    			if (fast.val != slow.val) { 
    				return false;
    			}
    			fast = fast.next;
    			slow = slow.next;
    		}
    		return true;
    	}
    
    	private ListNode reverse(ListNode head) { 
    		ListNode prev = null;
    		while (head != null) { 
    			ListNode next = head.next;
    			head.next = prev;
    			prev = head;
    			head = next;
    		}
    		return prev;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList;
    
    public class PalindromeLinkedListTest { 
    
    	@Test
    	public void test() { 
    		PalindromeLinkedList obj = new PalindromeLinkedList();
    
    		assertFalse(obj.isPalindrome1(SinglyLinkedList.ints2List(1, 2)));
    		assertTrue(obj.isPalindrome1(SinglyLinkedList.ints2List(1, 2, 2, 1)));
    		
    		assertFalse(obj.isPalindrome2(SinglyLinkedList.ints2List(1, 2)));
    		assertTrue(obj.isPalindrome2(SinglyLinkedList.ints2List(1, 2, 2, 1)));
    		
    		assertFalse(obj.isPalindrome3(SinglyLinkedList.ints2List(1, 2)));
    		assertTrue(obj.isPalindrome3(SinglyLinkedList.ints2List(1, 2, 2, 1)));
    		
    		assertFalse(obj.isPalindrome4(SinglyLinkedList.ints2List(1, 2)));
    		assertTrue(obj.isPalindrome4(SinglyLinkedList.ints2List(1, 2, 2, 1)));
    	}
    }

[https_leetcode.com_problems_palindrome-linked-list]: https://leetcode.com/problems/palindrome-linked-list/