# 如何对链表进行排序，该列表按升序和降序交替排序？

## 本文概述

``````Input List: 10 -> 40 -> 53 -> 30 -> 67 -> 12 -> 89 -> NULL
Output List: 10 -> 12 -> 30 -> 43 -> 53 -> 67 -> 89 -> NULL

Input List: 1 -> 4 -> 3 -> 2 -> 5 -> NULL
Output List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL``````

• 时间复杂度：链表的合并排序需要O(n log n)时间。在合并排序树中, 高度为log n。对每个级别进行排序将花费O(n)时间。因此, 时间复杂度为O(n log n)。
• 辅助空间：O(n log n), 在合并排序树中, 高度为log n。存储每个级别将占用O(n)空间。因此, 空间复杂度为O(n log n)。

1. 分开两个列表。
2. 以降序反转
3. 合并两个列表。

## C ++

``````//C++ program to sort a linked
//list that is alternatively
//sorted in increasing and decreasing order
#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

//This is the main function that sorts the
{
//Split the list into lists

}

//A utility function to create a new node
Node* newNode( int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}

//A utility function to reverse a linked list
{
Node *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}

//A utility function to print a linked list
{
}
cout <<endl;
}

//A utility function to merge two sorted linked lists
{
//Base cases

Node* temp = NULL;
}
else {
}
return temp;
}

//This function alternatively splits
//For example, 10->20->30->15->40->7 \
//is splitted into 10->30->40
//and 20->15->7
{
//Create two dummy nodes to initialize

while (curr) {
ascn->next = curr;
ascn = ascn->next;
curr = curr->next;

if (curr) {
dscn->next = curr;
dscn = dscn->next;
curr = curr->next;
}
}

ascn->next = NULL;
dscn->next = NULL;
}

//Driver program to test above function
int main()
{

cout <<"Given Linked List is " <<endl;

cout <<"Sorted Linked List is " <<endl;

return 0;
}``````

## Java

``````//Java program to sort a
//sorted in increasing and decreasing order

class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}

Node newNode( int key)
{
return new Node(key);
}

/* This is the main function that sorts
void sort()
{
/* Create 2 dummy nodes and initialise as
Node Ahead = new Node( 0 ), Dhead = new Node( 0 );

//Split the list into lists

//reverse the descending list

}

/* Function to reverse the linked list */
{
Node prev = null ;
Node next;
while (current != null ) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}

/* Function to print linked list */
void printList()
{
while (temp != null ) {
System.out.print(temp.data + " " );
temp = temp.next;
}
System.out.println();
}

//A utility function to merge
{
//Base cases

Node temp = null ;
}
else {
}
return temp;
}

//This function alternatively splits
//For example, 10->20->30->15->40->7 is
//splitted into 10->30->40
//and 20->15->7
{

while (curr != null ) {
//Link alternate nodes in ascending order
ascn.next = curr;
ascn = ascn.next;
curr = curr.next;

if (curr != null ) {
dscn.next = curr;
dscn = dscn.next;
curr = curr.next;
}
}

ascn.next = null ;
dscn.next = null ;
}

/* Driver program to test above functions */
public static void main(String args[])
{

llist.printList();

llist.sort();

llist.printList();
}

} /* This code is contributed by Rajat Mishra */``````

## python

``````# Python program to sort a linked list that is alternatively
# sorted in increasing and decreasing order
def __init__( self ):

class Node( object ):
def __init__( self , d):
self .data = d
self . next = None

def newNode( self , key):
return self .Node(key)

# This is the main function that sorts
def sort( self ):
# Create 2 dummy nodes and initialise as
Ahead = self .Node( 0 )
Dhead = self .Node( 0 )
# Split the list into lists
# reverse the descending list
# merge the 2 linked lists

# Function to reverse the linked list
prev = None
while current ! = None :
self ._next = current. next
current. next = prev
prev = current
current = self ._next

# Function to print linked list
def printList( self ):
while temp ! = None :
print temp.data, temp = temp. next
print ''

# A utility function to merge two sorted linked lists
# Base cases
if head1 = = None :
if head2 = = None :
temp = None
else :
return temp

# For example, 10->20->30->15->40->7 is splitted into 10->30->40
# and 20->15->7
while curr ! = None :
# Link alternate nodes in ascending order
ascn. next = curr
ascn = ascn. next
curr = curr. next
if curr ! = None :
dscn. next = curr
dscn = dscn. next
curr = curr. next
ascn. next = None
dscn. next = None

# Driver program
llist.head. next = llist.newNode( 40 )
llist.head. next . next = llist.newNode( 53 )
llist.head. next . next . next = llist.newNode( 30 )
llist.head. next . next . next . next = llist.newNode( 67 )
llist.head. next . next . next . next . next = llist.newNode( 12 )
llist.head. next . next . next . next . next . next = llist.newNode( 89 )

llist.printList()

llist.sort()

llist.printList()

# This code is contributed by BHAVYA JAIN``````

## C#

``````//C# program to sort a linked list that is alternatively
//sorted in increasing and decreasing order
using System;

public class Node {
public int data;
public Node next;
public Node( int d)
{
data = d;
next = null ;
}
}

Node newNode( int key)
{
return new Node(key);
}

/* This is the main function that sorts
void sort()
{
/* Create 2 dummy nodes and initialise as

//Split the list into lists

//reverse the descending list

}

/* Function to reverse the linked list */
{
Node prev = null ;
Node next;
while (current != null ) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}

/* Function to print linked list */
void printList()
{
while (temp != null ) {
Console.Write(temp.data + " " );
temp = temp.next;
}
Console.WriteLine();
}

//A utility function to merge two sorted linked lists
{
//Base cases

Node temp = null ;
}
else {
}
return temp;
}

//For example, 10->20->30->15->40->7 is splitted into 10->30->40
//and 20->15->7
{

while (curr != null ) {
//Link alternate nodes in ascending order
ascn.next = curr;
ascn = ascn.next;
curr = curr.next;

if (curr != null ) {
dscn.next = curr;
dscn = dscn.next;
curr = curr.next;
}
}

ascn.next = null ;
dscn.next = null ;
}

/* Driver code */
public static void Main(String[] args)
{

llist.printList();

llist.sort();

llist.printList();
}
}

/* This code is contributed by Arnab Kundu */``````

``````Given Linked List is
10 40 53 30 67 12 89
10 12 30 40 53 67 89``````

• 时间复杂度：O(n)。
需要遍历以分隔列表并将其反转。排序列表的合并需要O(n)时间。
• 辅助空间：O(1)。
不需要额外的空间。

• 回顶