排序双向链表的问题（java 空指针）

Question

我正在尝试解决 hackerrank 上的问题。要解决的问题是

"You’re given the pointer to the head node of a sorted doubly linked list and an integer to insert into the list. Create a node and insert it into the appropriate position in the list. The head node might be NULL to indicate that the list is empty."

他们提供的节点class定义为

/*
Insert Node at the end of a linked list 
head pointer input could be NULL as well for empty list
Node is defined as 

class Node {
    int data;
    Node next;
    Node prev;
}
*/

我尝试的解决方案是

Node SortedInsert(Node head,int data) 
{
    // new node to insert into linked list
    Node newNode = new Node();
    newNode.data = data;

    if (head == null)
    {  
        return newNode;
    }

    else
    {
        // start at beginning of list
        Node cur = head;

        // traverse through sorted list
        while (cur != null && cur.next != null)
        {        
            if (data < cur.next.data)
            {
                newNode.next = cur.next;
                newNode.prev = cur;
                cur.next.prev = newNode;
                cur.next = newNode;

                return head;
            }

            else
            {
                cur = cur.next;
            }
        }

        return head;
    }
}

我不太确定这里出了什么问题，但是 hackerrank 说我的解决方案不正确。知道可能出了什么问题吗？

Answer 1

假设我们的 DLL 是 1=2=3=4=5

现在考虑这种情况：将 6 添加到 DLL 循环不包括极端情况。

    while (cur != null && cur.next != null)
    {        
        if (data < cur.next.data)
        {
            newNode.next = cur.next;
            newNode.prev = cur;
            cur.next.prev = newNode;
            cur.next = newNode;

            return head;
        }

        else
        {
            cur = cur.next;
        }
    }

修改：

    if(data < cur.data) {
            newNode.next = cur;
            newNode.prev = null;
            cur.prev = newNode;

            head  = newNode;
            return head;
    }

    while (cur != null)
    {        
        if (data >= cur.data)
        {   
            if(cur.next == null) {
                 newNode.next = cur.next;
                 newNode.prev = cur;
                 cur.next = newNode;

                 return head;    
            }

            newNode.next = cur.next;
            newNode.prev = cur;
            cur.next.prev = newNode;
            cur.next = newNode;

            return head;
        }

        else
        {
            cur = cur.next;
        }
    }

排序双向链表的问题（java 空指针）

Trouble with sorted doubly linked list (java null pointer)

java

data-structures

nullpointerexception

doubly-linked-list