链表经典面试题之一讲

什么是链表？

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

今天给大家分享一道经典的单链表面试题

力扣题目——反转链表https://leetcode.cn/problems/reverse-linked-list/

只给了头节点head，要将这个链表反转，那我们就要考虑怎么才能将这个链表反转呢？

其实我们可以改变链表的指向：

如上图，要将链表反转，我们可以把1指向2，改成2指向，依次改指向，就可以把链表倒置，我们如果将原本的结点1指向2，改成节点指向1，那就原本2指向的结点3就找不到了，所以，我们要提前保存要改变指向的节点的下一个结点防止改变指向后丢失后面的结点

struct ListNode* n1=NULL;
struct ListNode* n2=head;
struct ListNode* n3=head->next;

我们定义3个结点，n1,n2,n3,让 n1=null,n2=phead,n3=phead->next;让n3保存n2的下一个结点，n2的下一个结点为n1，然后把n2赋给n1,把n3赋给n2,即

当n2为NULL的时候停下，返回n1就可以啦

while(n2)
    {
       n2->next=n1;
       n1=n2;
       n2=n3;
       n3=n3->next;
    }
return n1;

 但是此时我们要想一下这样就结束了吗？我们考虑到n2为空的时候循环停止，那此时n3即n2->next是不是已经为NULL了呢？，所以我们要在n3=n3->next的前面判断一下，当n3为NULL时就停止，即代码为

while(n2)
    {
       n2->next=n1;
       n1=n2;
       n2=n3;
       if(n3)
       n3=n3->next;
    }
return n1;

 到这里同志们是不是就以为万事大吉了呢?,我们定义n3的时候定义的是n2->next,有没有一种可能这是一个空链表呢？

所以，我们要在代码开始的时候判断一下如果链表为NULL的情况

if(head==NULL)
    {
        return NULL;
    }

到这里就可以完整结束了

完整代码如下：

struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    struct ListNode* n3=head->next;
    while(n2)
    {
       n2->next=n1;
       n1=n2;
       n2=n3;
       if(n3)
       n3=n3->next;
    }
    return n1;
}