在预先排序的链表中插入一个节点

Question

我一直在研究关于 hacker rank 的链表问题，我目前正在解决这个问题，它会要求你在一个排序的双向链表中插入一个节点。

这是我在Java

中写的逻辑

Node SortedInsert(Node head,int data) {

    Node newNode = new Node();
    Node temp = head;
    newNode.data = data;
    newNode.next = null;
    newNode.prev = null;

    if(head == null){
        head = newNode;
    }else{
        while(data > temp.data && temp.next != null){
            temp = temp.next;
        }
        if(temp == head){
            newNode.next = temp;
            temp.prev = newNode;
            head = newNode;
        }else if(data > temp.data){
            newNode.prev = temp;
            temp.next = newNode;
        }else{
            newNode.prev = temp.prev;
            newNode.next = temp;
            temp.prev.next = newNode;
            temp.prev = newNode;
        }

    }

  return head;
}

这是我得到的错误。

Your Output (stdout)
Wrong Answer!
Some possible errors:
1. You returned a NULL value from the function. 
2. There is a problem with your logic
Wrong Answer!
Some possible errors:
1. You returned a NULL value from the function. 
2. There is a problem with your logic

我不知道我做错了什么。我真的很想知道我哪里做错了。我知道在网上很容易找到答案，但我想如果有人能纠正我的错误，我会学到最好的。

Answer 1

问题是您总是在第一个元素之前插入列表中的第二个元素。考虑下图：

让链表初始为空。现在你按照你的算法插入 1。 head == null 案例被触发，head 现在指向 newNode。

x<-1->x
   |
  HEAD

现在，您尝试在列表中插入 2。您会看到 while 循环结束并且 temp 现在指向 head，触发后面的 if 条件 (if(temp == head)).

x<-1->x
   |
  HEAD, temp

这会插入 2（不正确！）before temp.

x<-2<=>1->x
   |
  HEAD

交换条件的顺序应该可以解决问题：

    if(data > temp.data) {    // First, check if you need to insert at the end.
        newNode.prev = temp;
        temp.next = newNode;
    } else if(temp == head) { // Then, check if you need to insert before head.
        newNode.next = temp;
        temp.prev = newNode;
        head = newNode;
    } else {                  // Otherwise, insert somewhere in the middle.
        newNode.prev = temp.prev;
        newNode.next = temp;
        temp.prev.next = newNode;
        temp.prev = newNode;
    }

在预先排序的链表中插入一个节点

Inserting a node in a pre sorted linked list

java

data-structures

linked-list

doubly-linked-list