[LC-148] Sort List.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sort a linked list in O(n log n) time using constant space complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__ (self,x):\n",
    "        self.val = x\n",
    "        self.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_link_list (l):\n",
    "    p = l\n",
    "    while p:\n",
    "        print p.val\n",
    "        p = p.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def print_list_array (l,arg):\n",
    "    p = l\n",
    "    temp = []\n",
    "    while p:\n",
    "        temp.append(p.val)\n",
    "        p = p.next\n",
    "    print (arg,temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# merge sort\n",
    "class Solution:\n",
    "    # @param {ListNode} head\n",
    "    # @return {ListNode}    \n",
    "    def sortList(self, head):\n",
    "        size, node = 0, head\n",
    "        while node:\n",
    "            node = node.next\n",
    "            size += 1\n",
    "        return self.merge_sort(head, size)\n",
    "\n",
    "    def merge_sort(self, head, size):\n",
    "        if size <= 1:\n",
    "            return head\n",
    "\n",
    "        right = prev = head\n",
    "        left_size = size/2\n",
    "        right_size = size - left_size\n",
    "\n",
    "        for i in range(left_size):\n",
    "            prev = right\n",
    "            right = right.next\n",
    "        prev.next = None  # divide list to two part\n",
    "        left = self.merge_sort(head, left_size)\n",
    "        right = self.merge_sort(right, right_size)\n",
    "        print_list_array (left,\"left: \")\n",
    "        print_list_array (right,\"right: \")\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    def merge(self, l1, l2):\n",
    "        vhead = curr = ListNode(0)\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                curr.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                curr.next = l2\n",
    "                l2 = l2.next\n",
    "            curr = curr.next\n",
    "        curr.next = l1 or l2\n",
    "        return vhead.next\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#quick sort\n",
    "class Solution2:\n",
    "    def helper(self, head):\n",
    "        if head is None or head.next is None:\n",
    "            return [head, head]\n",
    "        elif head.next.next is None:\n",
    "            if head.val <= head.next.val:\n",
    "                return [head, head.next]\n",
    "            else:\n",
    "                # reverse the list\n",
    "                next = head.next\n",
    "                next.next,head.next = head, None\n",
    "                return [next, head]\n",
    "        else:\n",
    "            base = head.val\n",
    "            hs, hm, hl = ListNode(-1), ListNode(-1), ListNode(-1)\n",
    "            ps, pm, pl = hs, hm, hl\n",
    "            p = head\n",
    "            while p is not None:\n",
    "                pn = p.next\n",
    "                p.next = None\n",
    "                if p.val < base:\n",
    "                    ps.next, ps = p, p\n",
    "                elif p.val == base:\n",
    "                    pm.next, pm = p, p\n",
    "                else:\n",
    "                    pl.next, pl = p, p\n",
    "                p = pn\n",
    "            [nhs, nts] = self.helper(hs.next)\n",
    "            [nhl, ntl] = self.helper(hl.next)\n",
    "            if nhl is None:\n",
    "                ntl = pm\n",
    "            pm.next = nhl\n",
    "            if nhs is not None:\n",
    "                nts.next = hm.next\n",
    "                return [nhs, ntl]\n",
    "            else:\n",
    "                return [hm.next, ntl]\n",
    "    # @param {ListNode} head\n",
    "    # @return {ListNode}\n",
    "    def sortList(self, head):\n",
    "        [h,t] = self.helper(head)\n",
    "        return h\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Init', [1, 4, 2, 10, 99, 0, 87, 12, 23, 34, 5, 3, 5])\n",
      "('return', [0, 1, 2, 3, 4, 5, 5, 10, 12, 23, 34, 87, 99])\n"
     ]
    }
   ],
   "source": [
    "#test cases:\n",
    "a = [1,4,2,10,99,0,87,12,23,34,5,3,5]\n",
    "b = [2,1]\n",
    "linklist = construct_list(a)\n",
    "print_list_array (linklist,\"Init\")\n",
    "solution = Solution2()\n",
    "ret = solution.sortList(linklist)\n",
    "print_list_array (ret,\"return\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#quick sort my own, NOT WORKING\n",
    "class Solution3:\n",
    "    def concatList (self,l1,l2,l3):\n",
    "        head = l1\n",
    "        tail = l1\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        tail.next = l2\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        tail.next = l3\n",
    "        while tail.next:\n",
    "            tail = tail.next    \n",
    "        return head\n",
    "    def sortList(self, head):\n",
    "        if head.next is None:\n",
    "            return head\n",
    "        else:\n",
    "            # Construct three linked lists to \n",
    "            lessHead,equalHead,greaterHead = ListNode(0),ListNode(0),ListNode(0)\n",
    "            pivot = head.val\n",
    "            p = head\n",
    "            while p is not None:\n",
    "                p = p.next\n",
    "                if p.val < pivot:\n",
    "                    # append value to \"less\" link list\n",
    "                    if lessHead.next is None:\n",
    "                        lessHead = p\n",
    "                        lessTail = lessHead\n",
    "                    else:\n",
    "                        lessTail.next = p\n",
    "                        lessTail = lessTail.next\n",
    "                elif p.val == pivot:\n",
    "                    if equalHead.next is None:\n",
    "                        equalHead = p\n",
    "                        equalTail = equalHead\n",
    "                    else:\n",
    "                        equalTail.next = p\n",
    "                        equalTail = equalTail.next\n",
    "                elif p.val > pivot:\n",
    "                    if greaterHead.next is None:\n",
    "                        greaterHead = p\n",
    "                        greaterTail = greaterHead\n",
    "                    else:\n",
    "                        greaterTail.next = p\n",
    "                        greaterTail = greaterTail.next\n",
    "                return self.sortList(self.concatList(lessHead,equalHead,greaterHead))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution4:\n",
    "    def toArray (self,l):\n",
    "        temp = []\n",
    "        i = 0\n",
    "        p = l\n",
    "        while p:\n",
    "            temp.append(p.val)\n",
    "            p = p.next\n",
    "        return temp\n",
    "    \n",
    "    def toList (self,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\n",
    "    \n",
    "    def sort(self,array=[12,4,5,6,7,3,1,15]):\n",
    "        less = []\n",
    "        equal = []\n",
    "        greater = []\n",
    "\n",
    "        if len(array) > 1:\n",
    "            pivot = array[0]\n",
    "            for x in array:\n",
    "                if x < pivot:\n",
    "                    less.append(x)\n",
    "                if x == pivot:\n",
    "                    equal.append(x)\n",
    "                if x > pivot:\n",
    "                    greater.append(x)\n",
    "            # Don't forget to return something!\n",
    "            return self.sort(less)+equal+self.sort(greater)  # Just use the + operator to join lists\n",
    "    # Note that you want equal ^^^^^ not pivot\n",
    "        else:  \n",
    "            return array\n",
    "    \n",
    "    def sortList (self,head):\n",
    "        a = self.toArray (head)\n",
    "        sortedArray = self.sort(a)\n",
    "        return self.toList(self.sort(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Init', [1, 4, 2, 10, 99, 0, 87, 12, 23, 34, 5, 3, 5])\n",
      "('Final', [0, 1, 2, 3, 4, 5, 5, 10, 12, 23, 34, 87, 99])\n"
     ]
    }
   ],
   "source": [
    "#test cases:\n",
    "a = [1,4,2,10,99,0,87,12,23,34,5,3,5]\n",
    "b = [2,1]\n",
    "linklist = construct_list(a)\n",
    "print_list_array (linklist,\"Init\")\n",
    "solution = Solution4()\n",
    "ret = solution.sortList(linklist)\n",
    "print_list_array (ret,\"Final\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def concatList (l1,l2):\n",
    "        head = l1\n",
    "        tail = l1\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        tail.next = l2\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        return head\n",
    "a = [1,4,2,10,99,0,87,12,23,34,5,3,5]\n",
    "b = [2,1,3]\n",
    "la = construct_list(a)\n",
    "lb = construct_list(b)\n",
    "print_list_array (concatList(la,lb),\"test\")"
   ]
  }
 ],
 "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
}