Логіка та Ефективні Алгоритми / Завдання на мові 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, а й вимагає розуміння роботи з покажчиками та реверсування пов'язаних списків. Вирішення таких завдань розвиває логічне мислення та здатність розробляти оптимальні алгоритми, що є ключовою навичкою для успішного програміста.