def is_palindrome_dict(head):
if not head or not head.next:<EOL><INDENT>return True<EOL><DEDENT>d = {}<EOL>pos = <NUM_LIT:0><EOL>while head:<EOL><INDENT>if head.val in d.keys():<EOL><INDENT>d[head.val].append(pos)<EOL><DEDENT>else:<EOL><INDENT>d[head.val] = [pos]<EOL><DEDENT>head = head.next<EOL>pos += <NUM_LIT:1><EOL><DEDENT>checksum = pos - <NUM_LIT:1><EOL>middle = <NUM_LIT:0><EOL>for v in d.values():<EOL><INDENT>if len(v) % <NUM_LIT:2> != <NUM_LIT:0>:<EOL><INDENT>middle += <NUM_LIT:1><EOL><DEDENT>else:<EOL><INDENT>step = <NUM_LIT:0><EOL>for i in range(<NUM_LIT:0>, len(v)):<EOL><INDENT>if v[i] + v[len(v) - <NUM_LIT:1> - step] != checksum:<EOL><INDENT>return False<EOL><DEDENT>step += <NUM_LIT:1><EOL><DEDENT><DEDENT>if middle > <NUM_LIT:1>:<EOL><INDENT>return False<EOL><DEDENT><DEDENT>return True<EOL>
This function builds up a dictionary where the keys are the values of the list,
and the values are the positions at which these values occur in the list.
We then iterate over the dict and if there is more than one key with an odd
number of occurrences, bail out and return False.
Otherwise, we want to ensure that the positions of occurrence sum to the
value of the length of the list - 1, working from the outside of the list inward.
For example:
Input: 1 -> 1 -> 2 -> 3 -> 2 -> 1 -> 1
d = {1: [0,1,5,6], 2: [2,4], 3: [3]}
'3' is the middle outlier, 2+4=6, 0+6=6 and 5+1=6 so we have a palindrome.