Insertion sort on a circularly linked list

Question

public void InsertionSortLL() {

Node start = tail.next; //First element in the circular LL

Node temp = start.next; //Comparing node

Node curr = start;

Node prev = null;

//Let's say I have a circularly linked list

// [3|4]--> [4|5] --> [5|2] --> [2|6] --> [6|3]

//Checks the first value and the second value

while((temp != tail)) {//not sure what the while loop should be

prev = start; // [3|4]

//curr = curr.next; []

//temp = temp.next;

if((temp.value <= curr.value)) {

curr = curr.next;

temp = temp.next;

}

if(temp.value >= start.value) {

curr.next = temp.next;

temp.next = curr;

}else {

curr.next = temp.next;

temp.next = start;

prev = temp;

start = prev;

curr = curr.next;

temp = temp.next;

}

}

if(temp == tail) {

if(curr.value <= temp.value) {

return;

}else {

prev = curr;

prev.next = temp.next;

temp.next = prev;

curr = prev;

}

}

}

I cannot figure out how to do an insertion sort.

If someone could help me out, that would be greatly appreciated.

Conceptual question:

Let's say I three nodes [1|3] --> [3|2] --> [2|1], which is a circular linked list (where [1|2] is the tail (no head pointer allowed in my code).

1. Set up [value | memory location?]

I want to organize by lowest value to highest (using the insertion sort), so here's how I interpret manipulating linked lists.

First, the value of the first node <= the value of the second node, so I will leave that.

start = tail.next; --> [1|3]

prev = start; -->[1|3]

curr = start;

temp = prev.next; --> 3, which leads to [3|2]

So skipping ahead, I want to switch the first and second nodes.

Is it correct that I want the second node to become [3|1] and the third node to become [2|3]? And is this how I would switch the two?

[3|2] is the current node

[2|1] is the temp node (also the tail node)

save = curr --> [3|2]

curr.next = temp.next.next (would this make curr = [3|1]?)

temp.next = save.next (would this make temp = [2|2]?)

Answer 1

https://scanftree. com/Data_Structure/insertion-in-circular-linked-list