Логика и Эффективные Алгоритмы / Задача на языке Java

Задача: Палиндромы в Списке

Допустим, у нас есть связанный список, и наша задача - определить, является ли он палиндромом. Палиндром - это последовательность, которая читается одинаково вперед и назад. 

Вы можете самостоятельно попробовать решить такую задачу или посмотреть решение ниже.

Решение к задаче

Давайте создадим Java-программу, чтобы решить эту увлекательную задачу.

В данной программе используется подход с "быстрым" и "медленным" указателями для нахождения середины списка и реверсирования второй половины. Затем происходит сравнение элементов первой и второй половин списка. Если все элементы совпадают, список считается палиндромом.

public class PalindromeLinkedList {

	static class ListNode {
		int val;
		ListNode next;

		ListNode(int val) {
			this.val = val;
		}
	}

	public static boolean isPalindrome(ListNode head) {
		if (head == null || head.next == null)
			return true;

		// Найти середину списка с использованием "быстрого" и "медленного" указателей
		ListNode slow = head, fast = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}

		// Реверсировать вторую половину списка
		ListNode secondHalf = reverseList(slow);

		// Сравнить первую половину с реверсированной второй половиной
		while (secondHalf != null) {
			if (head.val != secondHalf.val)
				return false;
			head = head.next;
			secondHalf = secondHalf.next;
		}

		return true;
	}

	private static ListNode reverseList(ListNode head) {
		ListNode prev = null;
		while (head != null) {
			ListNode next = head.next;
			head.next = prev;
			prev = head;
			head = next;
		}
		return prev;
	}

	public static void main(String[] args) {
		// Пример использования:
		ListNode list = new ListNode(1);
		list.next = new ListNode(2);
		list.next.next = new ListNode(3);
		list.next.next.next = new ListNode(2);
		list.next.next.next.next = new ListNode(1);

		System.out.println(isPalindrome(list)); // Вывод: true
	}
}

Эта задача не только проверяет знание базовых структур данных и алгоритмов в Java, но и требует понимания работы с указателями и реверсирования связанных списков. Решение таких задач развивает логическое мышление и способность разрабатывать оптимальные алгоритмы, что является ключевым навыком для успешного программиста.