链表 | 第7课（获取第N个结点）

编写一个函数 GetNth()，输入参数是一个链表和一个索引值，然后这个索引位置的结点值。

例如:

Input:  1->10->30->14,  index = 2
Output: 30  
The node at index 2 is 30

算法:

1. 初始化 count = 0
2. 循环链表
     a. 如果 count 等于输入的索引，就返回当前结点
         node
     b. 递增 count
     c. 当前指针后移

实现:

// C program to find n'th node in linked list
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

/* Given a reference (pointer to pointer) to the head
    of a list and an int, push a new node on the front
    of the list. */
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;
}

/* Takes head pointer of the linked list and index
    as arguments and return data at index*/
int GetNth(struct Node* head, int index)
{
    struct Node* current = head;
    int count = 0; /* the index of the node we're currently
                  looking at */
    while (current != NULL)
    {
       if (count == index)
          return(current->data);
       count++;
       current = current->next;
    }

    /* if we get to this line, the caller was asking
       for a non-existent element so we assert fail */
    assert(0);              
}

/* Drier program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;

    /* Use push() to construct below list
     1->12->1->4->1  */
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);  

    /* Check the count function */
    printf("Element at index 3 is %d", GetNth(head, 3));  
    getchar();
}

Output:
Element at index 3 is 4

时间复杂度: O(n)

方法 2- 使用递归

算法:

getnth(node,n)
1. 初始化 count = 1
2. if count == n
     return node->data
3. else
    return getnth(node->next,n-1)

实现:

// C program to find n'th node in linked list 
// using recursion
#include <bits/stdc++.h>
using namespace std;

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

/*  Given a reference (pointer to pointer) to 
    the head of a list and an int, push a 
    new node on the front of the list. */
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;
}

/* Takes head pointer of the linked list and index
    as arguments and return data at index*/
int GetNth(struct Node *head,int n)
{
    int count = 1;

    //if count equal too n return node->data
    if(count == n)
    return head->data;

    //recursively decrease n and increase 
    // head to next pointer 
    return GetNth(head->next, n-1); 
}

/* Drier program to test above function*/
int main()
{
     /* Start with the empty list */
    struct Node* head = NULL;

    /* Use push() to construct below list
     1->12->1->4->1  */
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);  

    /* Check the count function */
    printf("Element at index 3 is %d", GetNth(head, 3));  
    getchar();
}

Output:
Element at index 3 is 1

时间复杂度: O(n)