Problem
Given a singly linked list with chars, check if the nodes are Palindromic.
For example, given linked list w -> o -> r -> d -> r -> o -> w, the output should be true
given linked list a -> b -> c -> d -> c the output should be false.
Solution
We can convert this linked list to string, then check inward from start and end index. The cost will be walk through the linked list then iterate the string as charArray again. time cost will be 2N and an extra space for string is needed.
A better way is to find the middle point of the linked list with fast-slow pointer. Then compare if the first and second half is the same. When fast pointer reaches end, the slow pointer is at middle (pointing either to start of the second half or the middle)
a b b a
a b a
Then we reverse the second half,
a b a b
a a b
Then we compare the if the two halves has the same characters.
This algorithm needs to walk through the first half twice and the second half two and half times, it cost (N/2 + N/2) + (N/4 + N/2 + N/2) = (9/4)N for linked list traversal, if we use in place reverse, we don't need extra string. So the space cost is O(1).
class PalindromicLinkedList {
private static class Node {
char value;
Node next;
public Node(char value, Node next) {
this.value = value;
this.next = next;
}
}
public static void main(String...args) {
//a -> b -> b -> a -> null
Node head = new Node('a', null);
head.next = new Node('a', head.next);
head.next = new Node('b', head.next);
head.next = new Node('b', head.next);
System.out.println(isPalindromic(head));
}
//a b a
// s
// f
private static Node getMid(Node head) {
Node slow = head;
Node fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 1 -> 2 -> 3 -> 4
// p
// c
// n
private static Node reverse(Node head) {
if(head.next == null) return head;
Node pre = head;
Node curr = head;
Node next = head;
next = curr.next;
curr.next = null;
pre = curr;
curr = next;
while(curr.next != null) {
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
curr.next = pre;
return curr;
}
public static boolean isPalindromic(Node head) {
if(head == null) return false;
if(head.next == null) return true;
Node mid = getMid(head);
Node secondHalf = reverse(mid);
Node firstHalf = head;
//a a b
// f s
while(firstHalf != null && secondHalf != null) {
if(firstHalf.value != secondHalf.value)
return false;
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
}
private static class Node {
char value;
Node next;
public Node(char value, Node next) {
this.value = value;
this.next = next;
}
}
public static void main(String...args) {
//a -> b -> b -> a -> null
Node head = new Node('a', null);
head.next = new Node('a', head.next);
head.next = new Node('b', head.next);
head.next = new Node('b', head.next);
System.out.println(isPalindromic(head));
}
//a b a
// s
// f
private static Node getMid(Node head) {
Node slow = head;
Node fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 1 -> 2 -> 3 -> 4
// p
// c
// n
private static Node reverse(Node head) {
if(head.next == null) return head;
Node pre = head;
Node curr = head;
Node next = head;
next = curr.next;
curr.next = null;
pre = curr;
curr = next;
while(curr.next != null) {
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
curr.next = pre;
return curr;
}
public static boolean isPalindromic(Node head) {
if(head == null) return false;
if(head.next == null) return true;
Node mid = getMid(head);
Node secondHalf = reverse(mid);
Node firstHalf = head;
//a a b
// f s
while(firstHalf != null && secondHalf != null) {
if(firstHalf.value != secondHalf.value)
return false;
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
}
The time cost is O(N) and the space cost is O(1)
