使用双指针在链表之间插入新节点

public class ListNode {
    int val;
    ListNode next;
  
    ListNode(int val) {
        this.val = val;
    }
}

public ListNode insertNode(ListNode head, int insertVal) {
    ListNode newNode = new ListNode(insertVal);
  
    // 处理空链表的情况
    if (head == null) {
        newNode.next = newNode;
        return newNode;
    }
  
    ListNode cur = head;
    ListNode prev = null;
    boolean insertPosFound = false;
  
    do {
        // 在链表的合适位置插入新节点
        if ((prev != null && prev.val <= insertVal && cur.val >= insertVal)
                || (prev != null && prev.val > cur.val && (insertVal >= prev.val || insertVal <= cur.val))
                || (prev == cur)) {
            prev.next = newNode;
            newNode.next = cur;
            insertPosFound = true;
            break;
        }
  
        prev = cur;
        cur = cur.next;
    } while (cur != head);
  
    // 没有找到合适的插入位置，则将新节点插入到链表末尾
    if (!insertPosFound) {
        prev.next = newNode;
        newNode.next = cur;
    }
  
    return head;
}