顺序单链表插入新节点的一种方法

在学习链表的时候我们都接触过单链表插入新结点的问题。其中有一类就是在顺序链表中插入新节点，并保持链表的递增或者递减性质。

最近看《C和指针》一书中提到了一种方法，我个人感觉不错，并且思想非常好。

这是最常见的思维：

//sll_node.h  
  
typedef struct Node  
{  
    int value;  
    Node *next;  
} Node;  

#include "sll_node.h"  
#include <stdio.h>  
  
#define TRUE    1  
#define FALSE   0  
  
// insertNode:把newValue的值插入到递增排序的链表中，正确返回TRUE，错误返回FALSE  
// rootp是链表的头指针。  
int insertNode(Node **rootp, int newValue)  
{  
    Node *newNode; // 新节点的指针  
    Node *previous; // 当前指针的前一个指针  
    Node *current; // 当前指针  
  
    current = *rootp; // 初始化  
    previous = NULL;  
  
    // 查找插入的位置  
    while (current != NULL && current->value < newValue)
    {
        previous = current;
        current = current->next;
    }
  
    // 给新节点分配空间  
    newNode = (Node *)malloc(sizeof(Node));  
    if (newNode == NULL)  
        return FALSE;  
    newNode->value = newValue;  
  
    // 更改新节点的前驱和后继节点  
    newNode->next = current;  
    if (previous == NULL) // 此时插入节点的为链表中第一个节点，修改头指针  
        *rootp = newNode;  
    else  
        previous->next = newNode;

    return TRUE;
}

我以前编写的时候也会用这样的方法：一个当前指针和指向当前指针之前的指针，这样需要讨论原链表是否为空。书中提到了一种抽象，每次插入新的节点，都是改变一个指向这个新节点的指针以及指向下一个节点，这样可以省略讨论插入的节点是否为第一个节点的步骤。代码如下：

#include "sll_node.h"
#include <stdio.h>

#define	FALSE	0
#define TRUE	1

// insertNode2:把newValue的值插入到递增排序的链表中，正确返回TRUE，错误返回FALSE
// nextp是指向当前节点的指针，最初是头指针
int insertNode2(Node **nextp, int newValue)
{
	Node *newNode; // 新节点指针
	Node *current; // 当前节点指针

	current = *nextp; // 最初当前节点为nextp指针指向的节点
	// 查找新插入节点的位置
	while (current != NULL && current->value < newValue)
	{
		nextp = &current->next;
		current = current->next;
	}

	// 为新节点分配内存
	newNode = (Node *)malloc(sizeof(Node));
	if (newNode == NULL)
		return FALSE;
	newNode->value = newValue;

	// 统一了插入的步骤。即：每次插入，都是前一个指针指向新节点，新节点指向下一个节点
	*nextp = newNode;
	newNode->next = current;

	return TRUE;
}

main函数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sll_node.h"

int insertNode(Node **rootp, int newValue);
int insertNode2(Node **nextp, int newValue);

int main()
{
	srand(time(0));

	Node *head = (Node *)malloc(sizeof(Node));
	head->next = NULL;

	for (int i = 0; i < 5; i++)
	{
		int temp = rand() % 50;
		printf("%d\n", temp);
		//insertNode(&head,temp);
		insertNode2(&head,temp);
	}
	
	Node *p = head->next;
	while (p != NULL)
	{
		printf("%d\n", p->value);
		p = p->next;
	}

	getchar();
	getchar();
	return 0;
}

因为我个人没有经过正经的课堂训练，自己考研才接触编程、数据结构之类的。看了很多对自学编程提的建议都是多编写，并且要有抽象的思想，所以将这个方法写了下来，可能对很对科班出身的人不算什么问题了吧。

我感觉这个抽象很好，希望是给自己编程道路的一个好的开端吧:)

同时，因为我在初学时发现测试代码也会花费很多时间，所以将完成的代码都贴了上来，而不仅仅是函数，希望也能帮助到更多的想我这样的初学者吧。