将最小和最大的移动到链表的头和尾

Question

如何返回一个头作为最小元素和尾作为最大的链表?

函数shiftSmallLarge()以链表的头节点为参数，两次移动后返回头指针。

static Node shiftSmallLarge(Node head){
if(head==null){
return null;
}
Node temp=head;
Node min=head;
Node max=head;
while(temp.next!=null){

if(temp.data<min.data){
min=temp;
}
if(temp.data>max.data){
max=temp;
}
temp=temp.next;
}

}

Answer 1

你可以用两个指针来初始化链表中的前一个节点，一个指针从null初始化，另一个指针从list的头初始化。迭代你初始化的其他节点，从头到你想要的节点，迭代第一个节点在第二个节点之前。

Answer 2

在0 (n)内完成。遍历链接列表。找到两个节点(最小节点&最小节点之前的节点)。同样地，找到另外两个节点(最大节点和在最大节点之前的节点)。现在将最小节点作为头部，并调整链接列表的连续性，因为最小节点之前有一个节点。同样，调整最后的最大节点，因为您有最大节点和它前面的节点。

Answer 3

我认为下面的代码将工作，但它太大，我不能减少它。如果你有更好的主意，请纠正我。

def shiftSmallLarge(head):
if not  head or not head.next:
return head
pre=None
minpre=None;maxpre=None
mini=head;maxi=head
curr=head
while(curr):
if curr.data<mini.data:
minpre=pre
mini=curr
if curr.data>maxi.data:
maxpre=pre
maxi=curr
pre=curr
curr=curr.next
if mini==head and maxi==pre:
return head
elif minpre==None:
maxpre.next=maxi.next
pre.next=maxi
maxi.next=None
return head
elif maxpre==None:
if maxi.next==mini :
pre.next=maxi
head=head.next
maxi.next=None
return head
head=head.next
minpre.next=mini.next
mini.next=head
head=mini
if pre != mini:
pre.next=maxi
else:
minpre.next=maxi
maxi.next=None
return head
else:
minpre.next=mini.next
mini.next=head
head=mini
if maxpre==mini:
minpre.next=maxi.next
else:
maxpre.next=maxi.next
pre.next=maxi
maxi.next=None
return head

Answer 4

将最小值和最大值移动到列表的头部和尾部

• 这个代码可以很好地解决这个问题

// Return the head of updated list
static Node shiftSmallLarge(Node head) {
// Write your code here
if(head == null || head.next == null) {
return head;
}
Node temp = head;
Node min = head, max = head;
// find minimum node and maximum node
while(temp != null) {
if(min.data > temp.data) {
min = temp;
}
if(max.data < temp.data) {
max = temp;
}
temp = temp.next;
} 
// if min is at head do not anything with min
if(head != min) {
// finding previous node of min
temp = head;
while(temp.next != min) {
temp = temp.next;
}
temp.next = min.next;

// add min to start of list
min.next = head;
head = min;
}

// finding previous node of max
temp = head;
while(temp.next != max) {
temp = temp.next;
}
temp.next = max.next;

// add max to end of list
temp = head;
while(temp.next != null) {
temp = temp.next;
}
max.next = null;
temp.next = max;

return head;
}