Share my C++ solution
It is quite easy if you swap value instead of pointer. check my insertionSortListV. Once you understand the "swap by value" version. then "swap by pointer" is e
It is quite easy if you swap value instead of pointer. check my insertionSortListV. Once you understand the "swap by value" version. then "swap by pointer" is easy too. check insertionSortListP.\n\n1. pi means pre-i.   like this:    A1->A2->pj->j->A5->A6-pi->i->... the 3 steps to swap i and j by pointer \n\n    SWAP(pi->next, pj->next, t);\n    SWAP(i->next, j->next, t);\n    SWAP(i, j, t);\n\nif  J is the head, there is no pj. in order to handle this special case normally. I set up an ListNode object in the stack, called  hd. let pj->hd, hd->next = j. \n\n    #define SWAP(a, b, t) {t = a; a = b; b = t;}\n    class Solution {\n    public:\n        ListNode *insertionSortListV(ListNode *head) {\n            ListNode *i, *j;\n            int v;\n    \n            for (i = head->next; i; i = i->next) {\n                for (j = head; j != i; j = j->next) {\n                    if (i->val < j->val)\n                        SWAP(i->val, j->val, v);\n                }\n            }\n            return head;\n        }\n    \n        ListNode *insertionSortListP(ListNode *head) {\n            ListNode hd(0);\n            ListNode *i, *j, *t, *pi, *pj;\n    \n            i = head->next;\n            j = head;\n            hd.next = head;\n            pi = head;\n            pj = &hd;\n            while (i) {\n                while (j != i) {\n                    if (i->val < j->val) {\n                        SWAP(pi->next, pj->next, t);\n                        SWAP(i->next, j->next, t);\n                        SWAP(i, j, t);\n                    }\n                    pj = j;\n                    j = j->next;\n                }\n                j = hd.next;\n                pj = &hd;\n                pi = i;\n                i = i->next;\n            }\n            return hd.next;\n    \n        }\n        ListNode *insertionSortList(ListNode *head) {\n            // 0 or 1 element, no need to sort.\n            if (!head || !head->next)\n                return head;\n    #if 0\n            return insertionSortListV(head);\n    #else\n            return insertionSortListP(head);\n    #endif\n        }\n    };
[]