大家好，我是安然无虞。

每篇前言

博客主页：安然无虞

作者认证：2021年博客新星Top2

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请铁汁批评斧正。

火爆专栏：蓝桥杯基础算法剖析
欢迎加入：比特社区

种一棵树最好的时间是十年前，其次是现在。 各位，共勉。

面试题：反转链表

原题链接：反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例：

解题思路1：翻指针方向

不过直接翻指针方向这个方法定义两个指针是翻不动的，需要定义三个指针，可能看下图很难理解，但是要结合代码去理解，最好自己能画一遍，尝试自己写一遍代码。初始代码：

struct ListNode* reverseList(struct ListNode* head)
{
   //判断特殊情况
   if(head == NULL)
       return NULL;
   struct ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
   while(n2)
   {
       n2->next = n1;
       n1 = n2;
       n2 = n3;
       //注意哦，当n3指向空指针时再执行n3 = n3->next;会导致空指针异常
       if(n3)
           n3 = n3->next;
   }
   return n1;
}

   

  

   
  
  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
   
15
   
16
   
17
  

完整代码：
优化后的代码：

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

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
  

是不是变得很简单，这样写也无需判断特殊情况。
完整代码：

解题思路2：头插法

之所以需要多定义一个指针，是因为要保证能找到下一个。
代码执行:

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* newHead = NULL;
   struct ListNode* cur = head;
   while(cur)
   {
       //之所以将next定义在循环里是为了防止head为空时造成野指针
       struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;
   }
   return newHead;
}

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
  

完整代码：

遇见安然遇见你，不负代码不负卿。

码字不易，求个三连 抱拳了兄弟们。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/123991025