Repository: TheAlgorithms/Java
Pull request #5617 (2024-10-06 15:43:32)

Palindrome singly linkedlist optimised approach
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5617?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `0%` with `27 lines` in your changes missing coverage. Please review.
> Project coverage is 54.65%. Comparing base [(`be8df21`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/be8df2188c716389de5150487c0862b80d88bd4e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`f3ce817`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f3ce8175271d6eab8a792ecfe9d8bf9486b41ac1?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 19 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5617?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...thealgorithms/misc/PalindromeSinglyLinkedList.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5617?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fmisc%2FPalindromeSinglyLinkedList.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9taXNjL1BhbGluZHJvbWVTaW5nbHlMaW5rZWRMaXN0LmphdmE=) | 0.00% | [27 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5617?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5617      +/-   ##
============================================
+ Coverage     52.95%   54.65%   +1.70%     
- Complexity     3309     3454     +145     
============================================
  Files           529      538       +9     
  Lines         15343    15610     +267     
  Branches       2925     2965      +40     
============================================
+ Hits           8125     8532     +407     
+ Misses         6882     6721     -161     
- Partials        336      357      +21     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5617?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/misc/PalindromeSinglyLinkedList.java b/src/main/java/com/thealgorithms/misc/PalindromeSinglyLinkedList.java
index 07286b39..8af8a9b0 100644
--- a/src/main/java/com/thealgorithms/misc/PalindromeSinglyLinkedList.java
+++ b/src/main/java/com/thealgorithms/misc/PalindromeSinglyLinkedList.java
@@ -30,4 +30,47 @@ public final class PalindromeSinglyLinkedList {
 
         return true;
     }
+
+    // Optimised approach with O(n) time complexity and O(1) space complexity
+
+    public static boolean isPalindromeOptimised(Node head) {
+        if (head == null || head.next == null) {
+            return true;
+        }
+        Node slow = head;
+        Node fast = head;
+        while (fast != null && fast.next != null) {
+            slow = slow.next;
+            fast = fast.next.next;
+        }
+        Node midNode = slow;
+
+        Node prevNode = null;
+        Node currNode = midNode;
+        Node nextNode;
+        while (currNode != null) {
+            nextNode = currNode.next;
+            currNode.next = prevNode;
+            prevNode = currNode;
+            currNode = nextNode;
+        }
+        Node left = head;
+        Node right = prevNode;
+        while (left != null && right != null) {
+            if (left.val != right.val) {
+                return false;
+            }
+            right = right.next;
+            left = left.next;
+        }
+        return true;
+    }
+    static class Node {
+        int val;
+        Node next;
+        Node(int val) {
+            this.val = val;
+            this.next = null;
+        }
+    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/misc/PalindromeSinglyLinkedListTest.java b/src/test/java/com/thealgorithms/misc/PalindromeSinglyLinkedListTest.java
index ae0d6ae0..0f0577d3 100644
--- a/src/test/java/com/thealgorithms/misc/PalindromeSinglyLinkedListTest.java
+++ b/src/test/java/com/thealgorithms/misc/PalindromeSinglyLinkedListTest.java
@@ -7,6 +7,8 @@ import com.thealgorithms.datastructures.lists.SinglyLinkedList;
 import org.junit.jupiter.api.Test;
 
 public class PalindromeSinglyLinkedListTest {
+
+    // Stack-based tests
     @Test
     public void testWithEmptyList() {
         assertTrue(PalindromeSinglyLinkedList.isPalindrome(new SinglyLinkedList()));
@@ -67,4 +69,74 @@ public class PalindromeSinglyLinkedListTest {
         exampleList.insert(20);
         assertFalse(PalindromeSinglyLinkedList.isPalindrome(exampleList));
     }
+
+    // Optimized approach tests
+    @Test
+    public void testOptimisedWithEmptyList() {
+        assertTrue(PalindromeSinglyLinkedList.isPalindromeOptimised(null));
+    }
+
+    @Test
+    public void testOptimisedWithSingleElement() {
+        PalindromeSinglyLinkedList.Node node = new PalindromeSinglyLinkedList.Node(100);
+        assertTrue(PalindromeSinglyLinkedList.isPalindromeOptimised(node));
+    }
+
+    @Test
+    public void testOptimisedWithOddLengthPositive() {
+        PalindromeSinglyLinkedList.Node node1 = new PalindromeSinglyLinkedList.Node(1);
+        PalindromeSinglyLinkedList.Node node2 = new PalindromeSinglyLinkedList.Node(2);
+        PalindromeSinglyLinkedList.Node node3 = new PalindromeSinglyLinkedList.Node(1);
+        node1.next = node2;
+        node2.next = node3;
+        assertTrue(PalindromeSinglyLinkedList.isPalindromeOptimised(node1));
+    }
+
+    @Test
+    public void testOptimisedWithOddLengthPositive2() {
+        PalindromeSinglyLinkedList.Node node1 = new PalindromeSinglyLinkedList.Node(3);
+        PalindromeSinglyLinkedList.Node node2 = new PalindromeSinglyLinkedList.Node(2);
+        PalindromeSinglyLinkedList.Node node3 = new PalindromeSinglyLinkedList.Node(1);
+        PalindromeSinglyLinkedList.Node node4 = new PalindromeSinglyLinkedList.Node(2);
+        PalindromeSinglyLinkedList.Node node5 = new PalindromeSinglyLinkedList.Node(3);
+        node1.next = node2;
+        node2.next = node3;
+        node3.next = node4;
+        node4.next = node5;
+        assertTrue(PalindromeSinglyLinkedList.isPalindromeOptimised(node1));
+    }
+
+    @Test
+    public void testOptimisedWithEvenLengthPositive() {
+        PalindromeSinglyLinkedList.Node node1 = new PalindromeSinglyLinkedList.Node(10);
+        PalindromeSinglyLinkedList.Node node2 = new PalindromeSinglyLinkedList.Node(20);
+        PalindromeSinglyLinkedList.Node node3 = new PalindromeSinglyLinkedList.Node(20);
+        PalindromeSinglyLinkedList.Node node4 = new PalindromeSinglyLinkedList.Node(10);
+        node1.next = node2;
+        node2.next = node3;
+        node3.next = node4;
+        assertTrue(PalindromeSinglyLinkedList.isPalindromeOptimised(node1));
+    }
+
+    @Test
+    public void testOptimisedWithOddLengthNegative() {
+        PalindromeSinglyLinkedList.Node node1 = new PalindromeSinglyLinkedList.Node(1);
+        PalindromeSinglyLinkedList.Node node2 = new PalindromeSinglyLinkedList.Node(2);
+        PalindromeSinglyLinkedList.Node node3 = new PalindromeSinglyLinkedList.Node(2);
+        node1.next = node2;
+        node2.next = node3;
+        assertFalse(PalindromeSinglyLinkedList.isPalindromeOptimised(node1));
+    }
+
+    @Test
+    public void testOptimisedWithEvenLengthNegative() {
+        PalindromeSinglyLinkedList.Node node1 = new PalindromeSinglyLinkedList.Node(10);
+        PalindromeSinglyLinkedList.Node node2 = new PalindromeSinglyLinkedList.Node(20);
+        PalindromeSinglyLinkedList.Node node3 = new PalindromeSinglyLinkedList.Node(20);
+        PalindromeSinglyLinkedList.Node node4 = new PalindromeSinglyLinkedList.Node(20);
+        node1.next = node2;
+        node2.next = node3;
+        node3.next = node4;
+        assertFalse(PalindromeSinglyLinkedList.isPalindromeOptimised(node1));
+    }
 }