自省和展望

自我提升
🗨️字数统计=313字 ⏳阅读时长≈1分钟

算法题

链表的存储反转

定义一个方法（函数），实现输入一个链表的头结点，然后可以反转这个链表的方向，并输出反转之后的链表的头结点。

链表结点的结构：

1
2
3
4
typedef struct Node{
    int data;
    Node *next;
} Node, *List;

两种方法：遍历法、递归法

遍历法

主要包括如下4步：

1）如果head为空，或者只有head这一个节点，return head即可；

2）从头到尾遍历链表，把reversedHead赋值给当前节点的next；

3）当前节点赋值给reversedHead；

4）遍历结束，return reversedHead。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node* reverseList(Node* head)
{
    if(head == NULL || head->next == NULL)
        return head;
    Node* reversedHead = NULL;
    Node* p = head;
 
    while(p != NULL)
    {
        Node* q = p;
        q->next = reversedHead;
        reversedHead = q;
        p = p->next;
    }
    return reversedHead;
}

递归法：

递归的实现方式主要有4步：

1）如果head为空，或者只有head这一个节点，return head即可；

2）先遍历head->next为首的链表，得到一个头结点newHead；

3）把head赋值给head->next->next， head->next为空；

4）返回newHead。

1
2
3
4
5
6
7
8
9
10
node* reverseList2(node* head)
{
    if(head == NULL || head->next == NULL)
        return head;
     
    node* newHead = reversedList2(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

开放题

高楼扔鸡蛋

https://www.pianshen.com/article/5717909966/

分享到