FilesExpand file tree

 master

/

LinkedListCheckPalindrome.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (86 loc) · 2.01 KB

 master

/

LinkedListCheckPalindrome.java

Copy path

Top

File metadata and controls

• Code
• Blame

88 lines (86 loc) · 2.01 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

package misc;

/**

* Algorithm:-

* 1) Get the middle of the linked list.

* 2) Reverse the second half of the linked list.

* 3) Check if the first half and second half are identical.

* 4) Construct the original linked list by reversing the second half again and attaching it back to the first half

*

*/

public class LinkedListCheckPalindrome {

class Node {

int data;

Node next;

public Node(int data) {

this.data = data;

this.next = null;

}

}

public int size;

public Node head = null;

public Node tail = null;

public void addNode(int data) {

Node node = new Node(data);

if(head == null) {

head = node;

tail = node;

} else {

tail.next = node;

tail = node;

}

size++;

}

public Node reverseList(Node temp) {

Node current = temp;

Node prevNode = null;

Node nextNode = null;

while(current != null) {

nextNode = current.next;

current.next = prevNode;

prevNode = current;

current = nextNode;

}

return prevNode;

}

public void isPalindrome() {

Node current = head;

boolean flag = true;

int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);

for(int i = 1; i < mid; i++) {

current = current.next;

}

Node revHead = reverseList(current.next);

while(head != null && revHead != null) {

if(head.data != revHead.data) {

flag = false;

break;

}

head = head.next;

revHead = revHead.next;

}

if(flag) {

System.out.println("\nLinkedList is Palondrome !!!");

} else {

System.out.println("\nLinkedList is not Palindrome !");

}

}

public void display() {

Node current = head;

System.out.print("Nodes of Singly linked list: ");

while(current != null) {

System.out.print(current.data + " ");

current = current.next;

}

System.out.println(" ");

}

public static void main(String[] args) {

LinkedListCheckPalindrome linkedList = new LinkedListCheckPalindrome();

linkedList.addNode(1);

linkedList.addNode(2);

linkedList.addNode(3);

linkedList.addNode(2);

linkedList.addNode(1);

linkedList.display();

linkedList.isPalindrome();

}

}