# How would you sort a linked list?

Posted by Interview**Answer**

The idea is to choose sorting algorithm, as usually QuickSort and then think about swaping strategy.

Consider following situation:

1. The nodes being compared are not adjacent and one of them is the first node.

2. The nodes being compared are not adjacent and none of them is the first node

3. The nodes being compared are adjacent and one of them is the first node.

4. The nodes being compared are adjacent and none of them is the first node.

Another good stratery is merge sort as it is easy to merge sorted linked lists.

```
```

void LinkedListMergeSort(struct node** headRef)

{

struct node* head = *headRef;

struct node* a;

struct node* b;

if ((head == NULL) || (head->next == NULL)) return;

splitLLInto2(head, &a, &b);

LinkedListMergeSort(&a);

LinkedListMergeSort(&b);

*headRef = merge2SortedLLs(a, b);

}