Java : add node in sorted doubly linked list

Question

我正在尝试在已排序的双向链表中添加几个节点。代码有问题，我无法弄清楚。我创建了两个节点 current 和 prev 这将有助于遍历。

/*
  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) {
    Node newnode = new Node();
    newnode.data = data;
    Node current = head;
    Node pre = null;
    if(head == null) {
        head = newnode;
        newnode.prev = null;
    } 
    else if (head.data >= newnode.data) {
        newnode.next = head;
        head.prev = newnode;
        head = newnode;
        return newnode;
    }

    while(current!=null && current.data <= newnode.data) {
        pre = current;
        current = current.next;

        newnode.prev = pre;
        pre.next = newnode;
        newnode.next = current;
        if (current != null) {
            current.prev = newnode;
        }
    }
    return head;      
}

Answer 1

您的代码存在以下问题:

• if (head == null) 缺少返回语句。
• else if 是一个 if。
• 您的代码修改了所有节点，而不是在正确位置执行一次插入，因此所有访问过的节点都已损坏。

这是一个工作版本:

Node sortedInsert(Node head, int data) {
    Node newnode = new Node();
    newnode.data = data;

    // head is null -> new Node is new list
    if (head == null)
        return newnode;

    // handle special case if data < head.data
    if (data < head.data) {
        newnode.next = head;
        head.prev = newnode;
        return newnode; // newnode is the new list head
    }

    // search position in list
    Node prev = head;
    for (; prev.next != null; prev = prev.next) {
        if (prev.next.data > data)
            break;
    }

    // insert behind prev
    newnode.next = prev.next;
    if (prev.next != null) {
        prev.next.prev = newnode;
    }
    prev.next = newnode;
    newnode.prev = prev;

    return head; // head did not change
}