Commit 37668d7
authored
LinkedList Palindrome check file added
Please review Thanks !1 parent 8b1cedb commit 37668d7
1 file changed
Lines changed: 87 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,87 @@ | |||
| 1 | + public class PalindromeList{ | ||
| 2 | + public static void main(String[] args){ | ||
| 3 | + | ||
| 4 | + MyNode root = MyNode.getSampleList(); | ||
| 5 | + System.out.println("Original List"); | ||
| 6 | + MyNode.display(root); | ||
| 7 | + System.out.println("Is the list palindrome ? "+isPalindrome(root)); | ||
| 8 | + | ||
| 9 | + } | ||
| 10 | + | ||
| 11 | + private static boolean isPalindrome(MyNode root){ | ||
| 12 | + | ||
| 13 | + MyNode fastPointer = root; | ||
| 14 | + MyNode slowPointer = root; | ||
| 15 | + | ||
| 16 | + while(fastPointer!=null){ | ||
| 17 | + fastPointer = fastPointer.next; | ||
| 18 | + if(fastPointer!=null){ | ||
| 19 | + fastPointer= fastPointer.next; | ||
| 20 | + } | ||
| 21 | + slowPointer = slowPointer.next; | ||
| 22 | + } | ||
| 23 | + | ||
| 24 | + MyNode starting = root; | ||
| 25 | + MyNode comparingNode = reverseList(slowPointer); | ||
| 26 | + | ||
| 27 | + while(comparingNode!=null){ | ||
| 28 | + if(comparingNode.data != starting.data){ | ||
| 29 | + return false; | ||
| 30 | + } | ||
| 31 | + comparingNode = comparingNode.next; | ||
| 32 | + starting = starting.next; | ||
| 33 | + } | ||
| 34 | + | ||
| 35 | + return true; | ||
| 36 | + | ||
| 37 | + } | ||
| 38 | + | ||
| 39 | + private static MyNode reverseList(MyNode root){ | ||
| 40 | + | ||
| 41 | + MyNode current = root; | ||
| 42 | + MyNode next = null; | ||
| 43 | + MyNode prev = null; | ||
| 44 | + | ||
| 45 | + while(current!=null){ | ||
| 46 | + next = current.next; | ||
| 47 | + current.next = prev; | ||
| 48 | + prev = current; | ||
| 49 | + current = next; | ||
| 50 | + } | ||
| 51 | + | ||
| 52 | + return prev; | ||
| 53 | + | ||
| 54 | + } | ||
| 55 | + } | ||
| 56 | + | ||
| 57 | + class MyNode{ | ||
| 58 | + | ||
| 59 | + public int data ; | ||
| 60 | + public MyNode next ; | ||
| 61 | + | ||
| 62 | + MyNode(int data){ | ||
| 63 | + this.data = data; | ||
| 64 | + } | ||
| 65 | + | ||
| 66 | + protected static MyNode getSampleList(){ | ||
| 67 | + MyNode root = new MyNode(1); | ||
| 68 | + root.next = new MyNode(2); | ||
| 69 | + root.next.next = new MyNode(3); | ||
| 70 | + root.next.next.next = new MyNode(3); | ||
| 71 | + root.next.next.next.next = new MyNode(2); | ||
| 72 | + root.next.next.next.next.next = new MyNode(1); | ||
| 73 | + //root.next.next.next.next.next.next = new MyNode(3); | ||
| 74 | + return root; | ||
| 75 | + } | ||
| 76 | + | ||
| 77 | + protected static void display(MyNode root){ | ||
| 78 | + | ||
| 79 | + MyNode temp = root; | ||
| 80 | + while(temp!=null){ | ||
| 81 | + System.out.print(temp.data+" "); | ||
| 82 | + temp = temp.next; | ||
| 83 | + } | ||
| 84 | + System.out.println(); | ||
| 85 | + | ||
| 86 | + } | ||
| 87 | + } | ||
0 commit comments