-
Notifications
You must be signed in to change notification settings - Fork 0
/
PalindromeListRecursive.java
73 lines (61 loc) · 1.82 KB
/
PalindromeListRecursive.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package LinkedLists;
import java.util.Scanner;
import LinkedLists.SinglyLinkedList.Node;
public class PalindromeListRecursive {
public static class Result{
public Result(Node<Integer> head, boolean b) {
node = head;
result = b;
}
private Node<Integer> node;
private boolean result;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
System.out.println("Please enter the size of the linked list: ");
int size = scanner.nextInt();
SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
for(int i=0;i<size;++i){
if(list.size() == 0)
list.addFirst(scanner.nextInt());
else
list.addLast(scanner.nextInt());
}
scanner.close();
Result res = isPalindrome(list.getHead(), listLength(list.getHead()));
System.out.println("The list is a palindrome: " +res.result);
}
/**
* @return the final result whether list is palindrome or not
*/
static Result isPalindrome(Node<Integer> head, int length){
if(head == null || length <= 0){
return new Result(head, true);
}
else if(length == 1){
return new Result(head.getNext(), true);
}
//recurse on the sublist
Result res = isPalindrome(head.getNext(), length - 2);
//if child calls are not palindrome, pass back up a failure
if(!res.result || res.node==null){
return res;
}
//checks if there is a match between the node and corresponding node on the other side
res.result = (head.getElement() == res.node.getElement());
//returns the corresponding node
res.node = res.node.getNext();
return res;
}
/**
* @return the number of elements in the linked list
*/
static int listLength(Node<Integer> node){
int size = 0;
while(node!=null){
size++;
node = node.getNext();
}
return size;
}
}