通过更改节点将快速排序算法应用于双向链表

Question

我需要使用快速排序算法对双向链表进行排序。使用递归进行排序。我的分区函数与我们在数组中使用的分区函数相同。 但是我很难跟踪每个列表中的当前头节点和尾节点。

public void sort() {
Node la = getLast(head);
last = la;
quickSort(head, last);
}
public void quickSort(Node newhead, Node newlast) {
if(newhead == null || newlast == null) {
return;
}
if(newhead == newlast) {
return;
}
Node parti = partition(newhead,newlast);
if(parti != head)
quickSort(newhead, parti.prev);
if(parti != last)
newlast = acualTail;
quickSort(parti.next, newlast);

}
public Node partition(Node newHead, Node newLast) {
//Node actHead = newHead;
//Node acLast = newLast;
Node current = newHead;
Node p = newLast;
while(current != p) {
if(current.data > p.data) {
Node next = current.next;
current.next.prev = current.prev;
if(current.prev != null)
current.prev.next = current.next;
current.next = newLast.next;
current.prev = newLast; 
newLast.next = current;
//head = next;
if(current == newHead)
newHead = next;
newLast = current;
current = next;
}
else {
current = current.next;
}
}

head= newHead;
last = newLast;
return p;
}

Answer 1

这就是我的做法。

public Node getLast(Node head) {
Node current = head;
while(current.next != null) {
current = current.next;
}
return current;
}
public void sort() {
Node la = getLast(head);
quickSort(head, la);
head = actualHead;
}
public void quickSort(Node head, Node last) {
if(head == last)
return;
if(head == null || last == null)
return;
if(last.next == head)
return;
Node partition = partition(head, last);
Node newHead = this.head;
Node newTail = this.last;

quickSort(newHead, partition.prev);
if(actualHead == null)
{
actualHead = newHead;
}
quickSort(partition.next, newTail);
}
public Node partition(Node head, Node last) {
Node current = head;
Node p = last;
while(current != p) {
if(current.data > p.data) {
Node next = current.next;
current.next.prev = current.prev;
if(current.prev != null)
current.prev.next = current.next;
current.next = last.next;
current.prev = last; 
last.next = current;
if(current == head)
head = next;
last = current;
current = next;
}
else {
current = current.next;
}
}
this.head = head;
this.last = last;
return p;
}