Time limit exceeded for java "insertion sort linked list"

I was working on LeetCode to practice myself with Java programming. I encountered a question about insertion sort a linked list. My code currently runs correctly, but it failed on an instance with more than 8000 nodes. I guessed there must be a bottleneck for my code and I need your help.

My code :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode in; // i's next
        ListNode jn; // j's next
        ListNode inn; // in's next

        // I was using i.next and j.next as the current node. I hope by doing so I can get the node before the current node. 

        for(ListNode i = head; i.next != null; i = i.next) { 
            for(ListNode j = dummy; j.next != i.next; j = j.next) {
                if(i.next.val < j.next.val) {
                     in = i.next; // recording necessary node
                     jn = j.next;
                     inn = in.next;

                    if(j.next == i) { // when i and j are adjacent
                        j.next = in;
                        in.next = jn;
                        jn.next = inn;    
                        i = in; // back step i when finish exchange
                    } else { // different strategy when they are not
                        j.next = in;
                        in.next = jn;

                        i.next = inn;
                        i = jn; // back step i when finish exchange 
                    }
                    break; 
                }
            }
        }
        return dummy.next;
    }
}

Its debugging information:

```
Input: 17 -> 15 -> 14 -> 14 -> 12 -> 11 -> 10 -> 10 -> 9 -> 8
Dummy: 0 -> 15 -> 17 -> 14 -> 14 -> 12 -> 11 -> 10 -> 10 ->

The culprit is i = jn; in the last else branch.

This is not needed because you know that the entire list from head to i should be sorted and you need to continue from the old i.next.

Take the following step:

a->b->d->f-> ... y->z->c->h
   ^                ^
   j                i

this is where you do the insert which results in

a->b->c->d->f->... y->z->h
   ^     ^
   j     i

This causes you to need to repeat a full scan for every time you need to advance i. This can easily cause the time complexity to rise to O(n^3) for a reverse sorted list.

You should have.

a->b->c->d->f->... y->z->h
   ^               ^
   j               i

The way to solve this would be to not advance i in the outer for loop so you can keep it pointing to z after the insertion. This also means that you can use the same insertion strategy in both cases

for(ListNode i = head; i.next != null; ) { 
        bool inserted = false;
        for(ListNode j = dummy; j.next != i.next; j = j.next) {
            if(i.next.val advance i
    }

StackExchange Code Review Q#121771, answer score: 7