[LC] Linked List Palindrome.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__ (self,x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "def construct_list (array):\n",
    "    head = ListNode (0)\n",
    "    for i in range (len(array)):\n",
    "        if i==0:\n",
    "            head = ListNode (array[i])\n",
    "            tail = head\n",
    "        else:\n",
    "            tail.next = ListNode (array[i])\n",
    "            tail = tail.next\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    # @param {ListNode} head\n",
    "    # @return {boolean}\n",
    "    def isPalindrome(self, head):\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        # slow becomes the head of second half list, with equal or one more node\n",
    "        # reverse second half of the list:\n",
    "        prev = None\n",
    "        cur = slow\n",
    "        while cur:\n",
    "            Next = cur.next\n",
    "            cur.next = prev\n",
    "            prev = cur\n",
    "            cur = Next\n",
    "        # now prev is the head of the reversed half list\n",
    "        first = head\n",
    "        second = prev\n",
    "        while first and counter >= 1:\n",
    "            print \"first.val: \",first.val\n",
    "            print \"second.val: \",second.val\n",
    "            if first.val != second.val:\n",
    "                print \"False\"\n",
    "                return False\n",
    "            first = first.next\n",
    "            second = second.next\n",
    "            counter -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first.val:  1\n",
      "second.val:  1\n",
      "first.val:  2\n",
      "second.val:  2\n",
      "first.val:  3\n",
      "second.val:  2\n",
      "False\n",
      "is not palindrome\n"
     ]
    }
   ],
   "source": [
    "# test case\n",
    "l = construct_list ([1,2,3,2,2,1])\n",
    "solution = Solution ()\n",
    "if solution.isPalindrome (l):\n",
    "    print \"is palindrome\"\n",
    "else:\n",
    "    print \"is not palindrome\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}