input: (true and false) or (false or true)
output: true

                or
           /           \
        and             or
     /      \         /     \
true        false   false    true

class TreeNode {
	String val;
	TreeNode left;
	TreeNode right;
}

public boolean evaluateExpression(TreeNode node) {
	if(node == null)
		throw new IllegalArgumentException();
	// we can also use switch case instead of this nested if else block
	if("and".equals(node.val)) {
		return evaluateExpression(node.left) && evaluateExpression(node.right);
	} else if("or".equals(node.val)) {
		return evaluateExpression(node.left) || evaluateExpression(node.right);
    } else if("true".equals(node.val)) {
		if(node.right != null || node.left != null)
			throw new IllegalArgumentException();
		return true;
    } else if("false".equals(node.val)) {
		if(node.right != null || node.left != null)
			throw new IllegalArgumentException();
		return false;
	}

	// if the val is anything other than "and" // "or" // "true" // "false"
	throw new IllegalArgumentException();
}

public boolean isPalindrome(String str) {
	if(str == null)
		return true;
	int l = 0;
	int r = str.length();
	while(l < r) {
		if(str.charAt(l++) != str.charAt(r--)
			return false;
    }
	return true;
}

input list node 1(->2->3)
output list of head nodes which covers all permutations of the input list:  [1(->2->3), 1(->3->2), 2(->1->3), 2(->3->1), 3(->1->2), 3(->2->1)]

class Node {
	int val;
	Node next;
	public Node(int val) {
		this.val = val;
    }
}

public List<Node> getAllPermutations(Node input) {
// do something
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public static void main(String[] args) {
        Node root = new Node(1);
        Node next = new Node(2);
        Node nextNext = new Node(3);
        root.next = next;
        next.next = nextNext;

        for (Node head: getAllPermutations(root)) {
            while(head != null) {
                System.out.print(head.val + "->");
                head = head.next;
            }
            System.out.println();
        }
    }

    public static List<Node> getAllPermutations(Node input) {
        List<Node> res = new ArrayList<>();
        if(input == null)
            return res;

        // finding input length, it can be used to see if we explore all elements in one permutation.
        // So we can add to res list, if visited set size == inputLength
        int length = 0;
        Node start = input;
        while(start != null) {
            length++;
            start = start.next;
        }

        Node dummyHead = new Node(-1);

        backtrack(res, new HashSet<>(), dummyHead, dummyHead, input, length);

        return res;
    }

    /**
     * @param res {@link List<Node>} result list to which the permutations needs to be added.
     * @param visited {@link Set<Integer>} set to maintain visited elements.
     * @param currHead {@link Node} node that represents head of the current permutation
     * @param curr {@link Node} node that represents current pointer (or tail) of the current permutation.
     * @param input {@link Node} node that represents the input for which we should find all the permutations.
     * @param inputLength {@code int} length that represents the total elements in input list. Can be used to check if the
     *                          current permutation has all the elements by checking size of visited set with this input length
     */
    private static void backtrack(List<Node> res, Set<Integer> visited, Node currHead, Node curr, Node input, int inputLength) {
        // checking if we explored all the listNodes
        // if yes visited set size will be equal to input length 
        if(visited.size() == inputLength) {
            // we should clone the list using deep copy instead of just maintaining the pointer
            // if we did not clone it we will be touching its reference in other permutations
            res.add(clone(currHead.next));
            return;
        }

        // basic permutation logic?
        // iterating from input head till the end
        for(Node i = input; i != null; i = i.next) {
            // the next value we want to check to add to list
            int nextVal = i.val;
            // if the current permutation already contains this nextVal. We should skip it.
            if(!visited.contains(nextVal)) {
                // mark it as explored
                visited.add(nextVal);
                curr.next = new Node(nextVal);
                backtrack(res, visited, currHead, curr.next, input, inputLength);
                // removed from explored or visited set
                // to explore it another permutation
                visited.remove(nextVal);
            }
        }
    }

    /**
     * @param node head if the List which needs to be cloned
     * @return {@link Node} a cloned copy of the input {@code node}
     */
    private static Node clone(Node node) {
        Node cloneHead = new Node(-1);
        Node clone = cloneHead;
        while(node != null) {
            clone.next = new Node(node.val);
            clone = clone.next;
            node = node.next;
        }
        return cloneHead.next;
    }
}

class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}