リンクリストを昇順に並べ替えます（リンクリストのソート）

リンクリストを指定して、ノードを昇順で並べ替える関数を記述します。

Practice this problem

アイデアは、 sortedInsert() リンクリストをソートする関数。空の結果リストから始めます。ソースリストを繰り返し処理し、 sortedInsert() その各ノードを結果リストに追加します。注意してください .next 結果リストに移動する前に、各ノードのフィールド。

以下は、それを示すC、Java、およびPythonプログラムです。

C

#include <stdio.h>

#include <stdlib.h>

//リンクリストノード

struct Node

{

int data;

struct Node* next;

};

//指定されたリンクリストを印刷するヘルパー関数

void printList(struct Node* head)

{

struct Node* ptr = head;

while (ptr)

{

printf("%d —> ", ptr->data);

ptr = ptr->next;

}

printf("NULL");

}

//リンクリストの先頭に新しいノードを挿入するヘルパー関数

void push(struct Node** head, int data)

{

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = *head;

*head = newNode;

}

//指定されたノードを正しいソート位置で指定されたものに挿入する関数

//昇順でソートされたリスト

void sortedInsert(struct Node** head, struct Node* newNode)

{

struct Node dummy;

struct Node* current = &dummy;

dummy.next = *head;

while (current->next != NULL && current->next->data < newNode->data) {

current = current->next;

}

newNode->next = current->next;

current->next = newNode;

*head = dummy.next;

}

//リストを指定して、ソートされた順序になるように変更します( `sortedInsert()`を使用)。

void insertSort(struct Node** head)

{

struct Node* result = NULL; //ここで答えを作成します

struct Node* current = *head; //元のリストを繰り返し処理します

struct Node* next;

while (current != NULL)

{

//トリッキー：変更する前に次のポインタに注意してください

next = current->next;

sortedInsert(&result, current);

current = next;

}

*head = result;

}

int main(void)

{

//入力キー

int keys[] = {6, 3, 4, 8, 2, 9};

int n = sizeof(keys)/sizeof(keys[0]);

//リンクリストのヘッドノードを指します

struct Node* head = NULL;

//リンクリストを作成します

for (int i = n-1; i >= 0; i--) {

push(&head, keys[i]);

}

insertSort(&head);

//リンクリストを印刷します

printList(head);

return 0;

}

ダウンロードコードを実行する

出力:

2 —> 3 —> 4 —> 6 —> 8 —> 9 —> NULL

Java

//リンクリストノード

class Node

{

int data;

Node next;

Node(int data, Node next)

{

this.data = data;

this.next = next;

}

Node() {}

}

class Main

{

//指定されたリンクリストを印刷するヘルパー関数

public static void printList(Node head)

{

Node ptr = head;

while (ptr != null)

{

System.out.print(ptr.data + " —> ");

ptr = ptr.next;

}

System.out.println("null");

}

//指定されたノードを正しいソート位置で指定された場所に挿入します

//昇順でソートされたリスト

public static Node sortedInsert(Node head, Node newNode)

{

Node dummy = new Node();

Node current = dummy;

dummy.next = head;

while (current.next != null && current.next.data < newNode.data) {

current = current.next;

}

newNode.next = current.next;

current.next = newNode;

return dummy.next;

}

//リストを指定して、ソートされた順序になるように変更します( `sortedInsert()`を使用)

public static Node insertSort(Node head)

{

Node result = null; //ここで答えを作成します

Node current = head; //元のリストを繰り返し処理します

Node next;

while (current != null)

{

//トリッキー：変更する前に次の参照に注意してください

next = current.next;

result = sortedInsert(result, current);

current = next;

}

return result;

}

public static void main(String[] args)

{

//入力キー

int[] keys = {6, 3, 4, 8, 2, 9};

//リンクリストのヘッドノードを指します

Node head = null;

//リンクリストを作成します

for (int i = keys.length - 1; i >= 0; i--) {

head = new Node(keys[i], head);

}

head = insertSort(head);

//リンクリストを印刷します

printList(head);

}

ダウンロードコードを実行する

出力:

2 —> 3 —> 4 —> 6 —> 8 —> 9 —> null

Python

#リンクリストノード

class Node:

def __init__(self, data=None, next=None):

self.data = data

self.next = next

# 特定のリンクリストを印刷する#ヘルパー関数

def printList(head):

ptr = head

while ptr:

print(ptr.data, end=' —> ')

ptr = ptr.next

print('None')

#特定のノードを正しいソート位置で特定のノードに挿入する関数

# 昇順でソートされた#リスト

def sortedInsert(head, newNode):

dummy = Node()

current = dummy

dummy.next = head

while current.next and current.next.data < newNode.data:

current = current.next

newNode.next = current.next

current.next = newNode

return dummy.next

#リストを指定して、ソートされた順序になるように変更します( `sortedInsert()`を使用)。

def insertSort(head):

result = None #はここで答えを構築します

current = head #は元のリストを繰り返し処理します

while current:

#トリッキー：変更する前に次の参照に注意してください

next = current.next

result = sortedInsert(result, current)

current = next

return result

if __name__ == '__main__':

#入力キー

keys = [6, 3, 4, 8, 2, 9]

#は、リンクリストのヘッドノードを指します

head = None

#はリンクリストを作成します

for i in reversed(range(len(keys))):

head = Node(keys[i], head)

head = insertSort(head)

#印刷リンクリスト

printList(head)

ダウンロードコードを実行する

出力:

2 —> 3 —> 4 —> 6 —> 8 —> 9 —> None

上記のソリューションの時間計算量は次のとおりです。 O(n²)、どこ n リンクリスト内のノードの総数であり、余分なスペースは必要ありません。リンクリストをソートするためのマージソートベースのアルゴリズムについては、以下を参照してください。 O(n.log(n)) 時間。

こちらも参照:

単一リンクリストのマージソートアルゴリズム– C、Java、Python

ソース： http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

リンクリストを昇順で並べ替える(リンクリストを並べ替える)

C

Java

Python