JavaScript implements linked list insertion sorting and linked list merging sorting

  • 2021-11-29 08:09:32
  • OfStack

This article introduces in detail the implementation of JavaScript linked list insertion sorting and linked list merging sorting, linked list merging sorting is to merge each part of the sort, and then merge in 1.

1. Linked list

1.1 Storage Representation of Linked Lists


// Storage representation of linked list 
typedef int ElemType;
typedef struct LNode
{
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

1.2 Basic Operations

Create a linked list:


/*
 *  Create a linked list. 
 *  Formal parameter num Is the length of the linked list, and the function returns the header pointer of the linked list. 
 */
LinkList CreatLink(int num)
{
  int i, data;
 
  //p Point to the last in the current linked list 1 Nodes, q Point to the node to be inserted. 
  LinkList head = NULL, p = NULL, q;
 
  for (i = 0; i < num; i++)
  {
    scanf("%d", &data);
    q = (LinkList)malloc(sizeof(LNode));
    q->data = data;
    q->next = NULL;
    if (i == 0)
    {
      head = q;
    }
    else
    {
      p->next = q;
    }
    p = q;
  }
  return head;
}

Output linked list:


/*
 *  Output linked list node value. 
 */
int PrintLink(LinkList head)
{
  LinkList p;
  for (p = head; p ;p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

2. Linked list insertion sorting

Basic idea: Assuming that the first n-1 nodes are ordered, insert the first n node into the appropriate position of the first node, so that the n nodes are ordered.

Implementation method:

The first node on the linked list is removed to become a linked list containing one node (head1), and the rest nodes naturally become another linked list (head2), at this time head1 is a linked list containing one node

An ordered linked list of 1 node;

The first node on the linked list head2 is removed and inserted into the proper position of the linked list head1, so that head1 is still ordered, and head1 becomes an ordered linked list containing two nodes at this time;

One node is removed from the linked list head2 in turn and inserted into the linked list head1 until the linked list head2 is empty. Finally, the linked list head1 contains all nodes, and the nodes are orderly.

Insert sort code:


/*
 *  Linked list insertion sorting ( From small to large ) . 
 *  Input: Head pointer of linked list, 
 *  Output: Head pointer of sorted linked list. 
 *  Implementation method: split the original linked list into two parts: linked list 1 Still with head Is the head pointer, and the linked list nodes are ordered. Linked list 2 With head2 Is the head pointer, and the linked list nodes are out of order. 
 *  To link the list 2 Insert nodes in the linked list in turn 1 And keep the linked list 1 Orderly. 
 *  Last linked list 1 Contains all nodes and is ordered. 
 */
LinkList LinkInsertSort(LinkList head)
{
  //current Points to the node currently to be inserted. 
  LinkList head2, current, p, q;
 
  if (head == NULL)
    return head;
 
  // No. 1 1 Secondary splitting. 
  head2 = head->next;
  head->next = NULL;
 
  while (head2)
  {
    current = head2;
    head2 = head2->next;
 
    // Find the insertion position, which is the node p And q Middle. 
    for (p = NULL, q = head; q && q->data <= current->data; p = q, q = q->next);
 
    if (q == head)
    {
      // Will current Insert the front. 
      head = current;
    }
    else
    {
      p->next = current;
    }
    current->next = q;
  }
  return head;
}

Complete source code:


/*
 *  Linked list insertion sorting, from small to large 
 */
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define TOTAL 10    // Length of linked list 

// Storage representation of linked list 
typedef int ElemType;
typedef struct LNode
{
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

LinkList CreatLink(int num);
LinkList LinkInsertSort(LinkList head);
int PrintLink(LinkList head);

/*
 *  Create a linked list. 
 *  Formal parameter num Is the length of the linked list, and the function returns the header pointer of the linked list. 
 */
LinkList CreatLink(int num)
{
  int i, data;

  //p Point to the last in the current linked list 1 Nodes, q Point to the node to be inserted. 
  LinkList head = NULL, p = NULL, q;

  for (i = 0; i < num; i++)
  {
    scanf("%d", &data);
    q = (LinkList)malloc(sizeof(LNode));
    q->data = data;
    q->next = NULL;
    if (i == 0)
    {
      head = q;
    }
    else
    {
      p->next = q;
    }
    p = q;
  }
  return head;
}

/*
 *  Linked list insertion sorting ( From small to large ) . 
 *  Input: Head pointer of linked list, 
 *  Output: Head pointer of sorted linked list. 
 *  Implementation method: split the original linked list into two parts: linked list 1 Still with head Is the head pointer, and the linked list nodes are ordered. Linked list 2 With head2 Is the head pointer, and the linked list nodes are out of order. 
 *  To link the list 2 Insert nodes in the linked list in turn 1 And keep the linked list 1 Orderly. 
 *  Last linked list 1 Contains all nodes and is ordered. 
 */
LinkList LinkInsertSort(LinkList head)
{
  //current Points to the node currently to be inserted. 
  LinkList head2, current, p, q;

  if (head == NULL)
    return head;

  // No. 1 1 Secondary splitting. 
  head2 = head->next;
  head->next = NULL;

  while (head2)
  {
    current = head2;
    head2 = head2->next;

    // Find the insertion position, which is the node p And q Middle. 
    for (p = NULL, q = head; q && q->data <= current->data; p = q, q = q->next);

    if (q == head)
    {
      // Will current Insert the front. 
      head = current;
    }
    else
    {
      p->next = current;
    }
    current->next = q;
  }
  return head;
}

/*
 *  Output linked list node value. 
 */
int PrintLink(LinkList head)
{
  LinkList p;
  for (p = head; p ;p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

int main()
{
  LinkList head;

  printf(" Input Total Number to create a linked list: \n");
  head = CreatLink(TOTAL);
  
  head = LinkInsertSort(head);
  printf(" After sorting: \n");
  PrintLink(head);
  putchar('\n');
  return 0;
}

3. Merge and sort linked lists

Basic idea: If the linked list is empty or contains 1 node, the linked list is naturally ordered. Otherwise, divide the linked list into two parts, merge and sort each part, and then merge the sorted two linked lists into one.

Merge sort code:


/*
 *  Linked list merge sorting ( From small to large ) . 
 *  Input: Head pointer of linked list, 
 *  Output: Head pointer of sorted linked list. 
 *  Recursive implementation method: link the list head It is divided into two parts, which are merged and sorted respectively, and then the sorted two parts are merged in 1 Get up. 
 *  Recursive end condition: the linked list for recursive sorting is empty or only 1 Nodes. 
 */
LinkList LinkMergeSort(LinkList head)
{
  LinkList head1, head2;
  if (head == NULL || head->next == NULL)
    return head;
 
  LinkSplit(head, &head1, &head2);
  head1 = LinkMergeSort(head1);
  head2 = LinkMergeSort(head2);
  head = LinkMerge(head1, head2);
  return head;
}

Among them, the linked list segmentation function is as follows. The basic idea is to use slow/fast pointer. See notes for the specific implementation method.


/*
 *  Linked list segmentation function. 
 *  To link the list head Divided into two parts head1 And head2 If the length of the linked list is odd, the extra nodes belong to the first 1 Part. 
 *  Implementation method: First, make the pointer slow/fast Point to the head of the chain, 
 *  And then make fast As the pointer moves forward two nodes, slow The pointer moves forward 1 Nodes, 
 *  Circulate until fast The pointer points to the end of the chain. At the end, slow Point to linked list head1 The tail of the chain. 
 */
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2)
{
  LinkList slow, fast;
 
  if (head == NULL || head->next == NULL)
  {
    *head1 = head;
    *head2 = NULL;
    return 0;
  }
  slow = head;
  fast = head->next;
  while (fast)
  {
    fast = fast->next;
    if (fast)
    {
      fast = fast->next;
      slow = slow->next;
    }
  }
  *head1 = head;
  *head2 = slow->next;
 
  // Note: 1 Be sure to link the list head1 The chain tail of is left empty. 
  slow->next = NULL;
  return 0;
}

Linked list merge function has two methods: recursive implementation and non-recursive implementation:

Non-recursive implementation:


/*
 *  Linked list merging. 
 *  Merge two ordered linked lists in 1 From, make the total linked list orderly. 
 *  Input: Linked list head1 And linked list head2
 *  Output: Merged linked list 
 *  Implementation method: link the list head2 Insert nodes in the linked list in turn head1 In the appropriate position in, so that head1 Is still an ordered linked list. 
 */
LinkList LinkMerge(LinkList head1, LinkList head2)
{
  LinkList p, q, t;
 
  if (!head1)
    return head2;
  if (!head2)
    return head1;
 
  // Initialization of loop variables, q Point to linked list head1 The current node in the, p For q The forerunner of. 
  p = NULL;
  q = head1;
  while (head2)
  {
    //t Is the node to be inserted. 
    t = head2;
    head2 = head2->next;
    // Find the insertion position, which is p And q Between. 
    for (;q && q->data <= t->data; p = q, q = q->next);
    if (p == NULL)
      head1 = t;
    else
      p->next = t;
    t->next = q;
    // Will the node t Insert into p And q Between and after, make p Re-point q The forerunner of. 
    p = t;
  }
  return head1;
}

Recursive implementation:


LinkList LinkMerge2(LinkList head1, LinkList head2)
{
  LinkList result;
 
  if (!head1)
    return head2;
  if (!head2)
    return head1;
 
  if (head1->data <= head2->data)
  {
    result = head1;
    result->next = LinkMerge(head1->next, head2);
  }
  else
  {
    result = head2;
    result->next = LinkMerge(head1, head2->next);
  }
  return result;
}

Complete source code:


/*
* 链表归并排序,由小到大。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define TOTAL 10    //链表长度

//链表的存储表示
typedef int ElemType;
typedef struct LNode
{
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

LinkList CreatLink(int num);
LinkList LinkMergeSort(LinkList head);
LinkList LinkMerge(LinkList head1, LinkList head2);
LinkList LinkMerge2(LinkList head1, LinkList head2);
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2);
int PrintLink(LinkList head);

/*
* 创建链表。
* 形参num为链表的长度,函数返回链表的头指针。
*/
LinkList CreatLink(int num)
{
  int i, data;

  //p指向当前链表中最后1个结点,q指向准备插入的结点。
  LinkList head = NULL, p = NULL, q;

  for (i = 0; i < num; i++)
  {
    scanf("%d", &data);
    q = (LinkList)malloc(sizeof(LNode));
    q->data = data;
    q->next = NULL;
    if (i == 0)
    {
      head = q;
    }
    else
    {
      p->next = q;
    }
    p = q;
  }
  return head;
}

/*
* 输出链表结点值。
*/
int PrintLink(LinkList head)
{
  LinkList p;
  for (p = head; p; p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

int main()
{
  LinkList head;

  printf("输入Total个数以创建链表:\n");
  head = CreatLink(TOTAL);

  head = LinkMergeSort(head);
  printf("排序后:\n");
  PrintLink(head);
  putchar('\n');
  return 0;
}

/*
 * 链表归并排序(由小到大)。
 * 输入:链表的头指针,
 * 输出:排序后链表的头指针。
 * 递归实现方法:将链表head分为两部分,分别进行归并排序,再将排序后的两部分归并在1起。
 * 递归结束条件:进行递归排序的链表为空或者只有1个结点。
 */
LinkList LinkMergeSort(LinkList head)
{
  LinkList head1, head2;
  if (head == NULL || head->next == NULL)
    return head;

  LinkSplit(head, &head1, &head2);
  head1 = LinkMergeSort(head1);
  head2 = LinkMergeSort(head2);
  head = LinkMerge(head1, head2);    //非递归实现
  //head = LinkMerge2(head1, head2);  //递归实现
  return head;
}

/*
 * 链表归并。
 * 将两个有序的链表归并在1起,使总链表有序。
 * 输入:链表head1和链表head2
 * 输出:归并后的链表
 * 实现方法:将链表head2中的结点依次插入到链表head1中的适当位置,使head1仍为有序链表。
 */
LinkList LinkMerge(LinkList head1, LinkList head2)
{
  LinkList p, q, t;

  if (!head1)
    return head2;
  if (!head2)
    return head1;

  //循环变量的初始化,q指向链表head1中的当前结点,p为q的前驱。
  p = NULL;
  q = head1;
  while (head2)
  {
    //t为待插入结点。
    t = head2;
    head2 = head2->next;
    //寻找插入位置,插入位置为p和q之间。
    for (;q && q->data <= t->data; p = q, q = q->next);
    if (p == NULL)
      head1 = t;
    else
      p->next = t;
    t->next = q;
    //将结点t插入到p和q之间后,使p重新指向q的前驱。
    p = t;
  }
  return head1;
}

LinkList LinkMerge2(LinkList head1, LinkList head2)
{
  LinkList result;

  if (!head1)
    return head2;
  if (!head2)
    return head1;

  if (head1->data <= head2->data)
  {
    result = head1;
    result->next = LinkMerge(head1->next, head2);
  }
  else
  {
    result = head2;
    result->next = LinkMerge(head1, head2->next);
  }
  return result;
}

/*
 * 链表分割函数。
 * 将链表head均分为两部分head1和head2,若链表长度为奇数,多出的结点从属于第1部分。
 * 实现方法:首先使指针slow/fast指向链首,
 * 然后使fast指针向前移动两个结点的同时,slow指针向前移动1个结点,
 * 循环移动,直至fast指针指向链尾。结束时,slow指向链表head1的链尾。
 */
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2)
{
  LinkList slow, fast;

  if (head == NULL || head->next == NULL)
  {
    *head1 = head;
    *head2 = NULL;
    return 0;
  }
  slow = head;
  fast = head->next;
  while (fast)
  {
    fast = fast->next;
    if (fast)
    {
      fast = fast->next;
      slow = slow->next;
    }
  }
  *head1 = head;
  *head2 = slow->next;

  //注意:1定要将链表head1的链尾置空。
  slow->next = NULL;
  return 0;
}


Related articles: