插入排序双向链表
Insertion in sorted doubly linked list
我得到了指向已排序双向链表头节点的指针和一个要插入到 list.I 中的整数,我被告知创建一个节点并将其插入到列表中的适当位置,这样它的排序顺序保持不变。头节点可能为 NULL。
示例输入
NULL,数据 = 2
空值 <-- 2 <--> 4 <--> 6 --> 空值,数据 = 5
示例输出
空值 <-- 2 --> 空值
空值 <-- 2 <--> 4 <--> 5 <--> 6 --> 空值
我尝试了上面的方法 problem.But 我的程序正在终止,因为 timeout.What 我在下面的代码中做错了吗?假设 Node class 并且 main 函数已经存在。非常感谢!!
Node SortedInsert(Node head,int data) {
Node newn = new Node();
newn.data = data;
newn.prev=null;
newn.next = null;
Node ptr = head;
Node nex=head.next;
while(ptr!=null && nex!=null) {
if(ptr.data<=newn.data && nex.data>=newn.data) {
newn.next = nex;
newn.prev = ptr;
nex.prev = newn;
ptr.next = newn;
}
else {
nex=nex.next;
ptr=ptr.next;
}
}
if(ptr!=null && nex==null) {
if(ptr.data>=newn.data) {
newn.next=ptr;
ptr.prev=newn;
newn.prev=null;
head=newn;
}
else {
ptr.next=newn;
newn.prev = head;
}
}
if(head==null) {
head = newn;
}
return head;
}
相当简单:
成功插入后,您不会跳出循环。因此它不断循环它插入节点的位置。做一个微小的改变:
if(ptr.data>=newn.data)
{
newn.next=ptr;
ptr.prev=newn;
newn.prev=null;
head=newn;
break;
}
但是,您编写了一些冗余代码。这更短并且不包含冗余代码:
Node SortedInsert(Node head,int data) {
Node newn = new Node();
newn.data = data;
Node ptr = head;
if (ptr == null) {
head = newn;
} else if ( ptr.data > newn.data ) {
newn.next = ptr;
ptr.prev = newn;
head = newn;
} else {
Node nex = head.next;
while (nex != null && nex.data <= newn.data) {
ptr = nex;
nex = nex.next;
}
ptr.next = newn;
newn.prev = ptr;
if (nex != null) {
nex.prev = newn;
newn.next = nex;
}
}
return head;
}
如果头节点为空,您将在尝试获取 next/prev 节点时遇到 NullPointerException。你应该先检查一下:
Node sortedInsert(Node head, int data) {
Node newn = new Node();
newn.data = data;
//Basic case: the list is empty, so the head is null
if (head==null) {
return newn;
}
//If node is not null
Node aux= head;
Node auxPrev;
while (aux!=null && aux.data<data) {
auxPrev=aux;
aux=aux.next;
}
//auxPrev will be null if we are going to insert in the first position
if (auxPrev!=null)
auxPrev.next=newn;
newn.prev=auxPrev;
head=newn;
}
//aux will be null if we insert in the last position
if (aux!=null) {
aux.prev=newn;
newn.next=aux;
}
return head;
}
我得到了指向已排序双向链表头节点的指针和一个要插入到 list.I 中的整数,我被告知创建一个节点并将其插入到列表中的适当位置,这样它的排序顺序保持不变。头节点可能为 NULL。
示例输入
NULL,数据 = 2
空值 <-- 2 <--> 4 <--> 6 --> 空值,数据 = 5
示例输出
空值 <-- 2 --> 空值
空值 <-- 2 <--> 4 <--> 5 <--> 6 --> 空值
我尝试了上面的方法 problem.But 我的程序正在终止,因为 timeout.What 我在下面的代码中做错了吗?假设 Node class 并且 main 函数已经存在。非常感谢!!
Node SortedInsert(Node head,int data) {
Node newn = new Node();
newn.data = data;
newn.prev=null;
newn.next = null;
Node ptr = head;
Node nex=head.next;
while(ptr!=null && nex!=null) {
if(ptr.data<=newn.data && nex.data>=newn.data) {
newn.next = nex;
newn.prev = ptr;
nex.prev = newn;
ptr.next = newn;
}
else {
nex=nex.next;
ptr=ptr.next;
}
}
if(ptr!=null && nex==null) {
if(ptr.data>=newn.data) {
newn.next=ptr;
ptr.prev=newn;
newn.prev=null;
head=newn;
}
else {
ptr.next=newn;
newn.prev = head;
}
}
if(head==null) {
head = newn;
}
return head;
}
相当简单: 成功插入后,您不会跳出循环。因此它不断循环它插入节点的位置。做一个微小的改变:
if(ptr.data>=newn.data)
{
newn.next=ptr;
ptr.prev=newn;
newn.prev=null;
head=newn;
break;
}
但是,您编写了一些冗余代码。这更短并且不包含冗余代码:
Node SortedInsert(Node head,int data) {
Node newn = new Node();
newn.data = data;
Node ptr = head;
if (ptr == null) {
head = newn;
} else if ( ptr.data > newn.data ) {
newn.next = ptr;
ptr.prev = newn;
head = newn;
} else {
Node nex = head.next;
while (nex != null && nex.data <= newn.data) {
ptr = nex;
nex = nex.next;
}
ptr.next = newn;
newn.prev = ptr;
if (nex != null) {
nex.prev = newn;
newn.next = nex;
}
}
return head;
}
如果头节点为空,您将在尝试获取 next/prev 节点时遇到 NullPointerException。你应该先检查一下:
Node sortedInsert(Node head, int data) {
Node newn = new Node();
newn.data = data;
//Basic case: the list is empty, so the head is null
if (head==null) {
return newn;
}
//If node is not null
Node aux= head;
Node auxPrev;
while (aux!=null && aux.data<data) {
auxPrev=aux;
aux=aux.next;
}
//auxPrev will be null if we are going to insert in the first position
if (auxPrev!=null)
auxPrev.next=newn;
newn.prev=auxPrev;
head=newn;
}
//aux will be null if we insert in the last position
if (aux!=null) {
aux.prev=newn;
newn.next=aux;
}
return head;
}