I wanted to solve this problem by changing pointers and not by copying the node values. While working on this problem, I came across below scenarios.

- left and right nodes are next to each other.
- left and right nodes are far(some nodes between them)
- General case is updating head pointer.

left node is fixed at position i ( 1 to n-1) and it will be compared with next i+1 to n nodes using right pointer. If left node is greater than right node then adjust the pointers such that left node becomes right and right becomes left node.

```
ListNode *insertionSortList(ListNode *head) {
if(head == nullptr)
return nullptr;
ListNode *left = head, *right = nullptr, *prevLeft = nullptr, *prevRight = nullptr;
bool firstNode = true;
while(left->next != nullptr) {
prevRight = nullptr;
right = left->next;
while(right != nullptr) {
if(left->val > right->val) {
ListNode *temp = left->next == right ? left : left->next;
left->next = right->next;
right->next = temp;
//swapping left and right to keep logic clear
temp = left; left = right; right = temp;
if(prevLeft)
prevLeft->next = left;
if(prevRight)
prevRight->next = right;
if(firstNode)
head = left;
}
prevRight = right;
right = right->next;
}
prevLeft = left;
left = left->next;
firstNode = false;
}
return head;
}
```