链表 | 第4课（链表的长度）

要求写一个 C 函数计算指定单链表的结点数。

例如, 链表1->3->1->2->1通过这个函数可以获取到 5 个结点。

迭代方案

1. 初始化计数为 0
2. 初始化一个结点指针, current = head.

3. 如果 current 不为 NULL 继续循环

   a) current = current -> next
   b) count++;

1. 返回计数

下面是 C/C++ 实现的计数算法。

#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};

/* 指向头结点的指针和一个整数, 在链表的头部添加一个新结点. */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));

    /* put in the data  */
    new_node->data  = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}

/* 获取链表的结点数 */
int getCount(struct Node* head)
{
    int count = 0;  // 初始值
    struct Node* current = head;  // 当前结点
    while (current != NULL)
    {
        count++;
        current = current->next;
    }
    return count;
}

/* 测试函数*/
int main()
{
    /* 开始空链表 */
    struct Node* head = NULL;

    /* 使用 push() 构造链表
     1->2->1->3->1  */
    push(&head, 1);
    push(&head, 3);
    push(&head, 1);
    push(&head, 2);
    push(&head, 1);

    /* 计数函数 */
    printf("count of nodes is %d", getCount(head));
    return 0;
}

输出:
count of nodes is 5

递归方案

int getCount(head)

1. 如果头结点为 NULL, 返回 0.
2. 否则返回 return 1 + getCount(head->next)

下面是 C/C++ 实现的递归算法。

#include<stdio.h>
#include<stdlib.h>

/* 链表结点 */
struct Node
{
    int data;
    struct Node* next;
};

/* 指向头结点的指针和一个整数, 在链表的头部添加一个新结点 */
void push(struct Node** head_ref, int new_data)
{
    /* 分配结点 */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));

    /* 指定数据  */
    new_node->data  = new_data;

    /* 指定新结点的后继为旧的头结点 */
    new_node->next = (*head_ref);

    /* 新结点成为头结点 */
    (*head_ref)    = new_node;
}

/* 计数函数*/
int getCount(struct Node* head)
{
    // 递归结束条件
    if (head == NULL)
        return 0;

    return 1 + getCount(head->next);
}

/* 测试函数*/
int main()
{
    /* 开始空链表 */
    struct Node* head = NULL;

    /* 使用 push() 构造链表
     1->2->1->3->1  */
    push(&head, 1);
    push(&head, 3);
    push(&head, 1);
    push(&head, 2);
    push(&head, 1);

    /* 计数函数 */
    printf("count of nodes is %d", getCount(head));
    return 0;
}

输出:
count of nodes is 5