牛客网 - 华为笔试题 - 循环链表

秒速五厘米 2022-10-24 11:48 208阅读 0赞

## 题目描述 ##

有一个数组a\[N\]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

## 解法 ##

*  循环链表
 *  判断条件

**循环链表**  
尾部节点的`next`指针指向首部节点的链表结构

**创建一个循环链表**

*  声明一个`head`节点指针，并开辟内存空间
 *  声明一个`temp`指针指向`head`，用于创建循环链表
 *  **1.赋值**：首先给`temp`指向的节点赋值
 *  **2.创建节点**：声明一个新的节点指针，并开辟内存空间
 *  **3.连接节点**：令`temp`的`next`指针指向该新节点
 *  **4.指向新节点**：`temp`指向这个新节点或者头节点(判断是否是最后一个节点)

## 代码 ##

#include<stdio.h>
    struct Node{ 
        // 整数
        int number;
        struct Node *next;
    };
    int main(){ 
        int n;
        // 输入N
        while(scanf("%d", &n)!=EOF){ 
            // 代码的鲁棒性
            if(n > 1000){ 
                n = 1000;
            }
            // 定义一个循环链表
            // 尾节点的next指向头节点
            int i = 0;
            // 创建头节点
            struct Node * head = malloc(sizeof(struct Node *));
            struct Node * temp = head;
            while(i < n){ 
                // 首先给temp节点赋值，然后创建一个节点，让temp指向这个节点
                temp->number = i;
                // 创建一个空节点
                struct Node *no = malloc(sizeof(struct Node*));
                // 1. 给temp->next连接一个节点，
                // 2. 让temp往后移动一位
                // 如果i == n-1
                if(i == n-1){ 
                    temp->next = head;
                }else{ 
                    temp->next = no;
                    temp = temp->next;
                }
                i++;
            }
            // 当head->next == head时，此时，head->next即是要找的值
            while(head->next != head){ 
                // 移动一次，删除一个，再移动一步
                // head->next = head->next->next;
                // 移动1次
                head = head->next;
                // 删除一个
                head->next = head->next->next;
                // 移动一步
                head = head->next;
            }
            printf("%d\n", head->next->number);
        }
    }