Leetcode-反转链表

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

链接206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

注意：如果是空链表的话，直接返回空指针

方法1：递归

• 把头的下一个结点进行递归
• 递归结束条件：链表遇到尾结点，开始返回
• 递归后的内容：将head后一个结点的next指向自己，然后把head的next置空
• 最后 newhead就是头结点

**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    //如果链表为空，然后head (此时head为空) 
    //链表到尾结点则结束递归
    if(head== NULL || head->next == NULL)
    {
        return head;
    }
    //递归
    struct ListNode* newhead = reverseList(head->next);
    //将箭头反转
    head->next->next = head;
    head->next = NULL;
    return newhead;
}

方法2：反转指针

==思路==：

定义3个指针变量

• n1：反转被指向的结点(即n2的前一个结点)
• n2：指针要反转的结点
• n3：保存n2的下一个结点

最初：n1为空 n2:头结点 n3：头结点的下一个结点

反转：把n2的next指向n1

迭代过程：把n2赋给n1 把n3赋给n2，然后n3 = n3->next 也就是三个指针变量都往后走

迭代结束条件：n2为空

由于最后一次反转时，n3为空，如果再进行n3 = n3->next 就相当于对空指针解引用，会出错，所以可以对n3进行判断，如果n3为空时，就不进行n3 = n3->next操作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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 != NULL)
   {
       //反转
       n2->next = n1;

       //迭代往后走
       n1 = n2;
       n2 = n3;
       //当n2指向尾结点的时候，n3为空，不能对空指针解引用，所以要单独判断
       if(n3)
       {
           n3 = n3->next;
       }
   }
   return n1;
}

**上述代码，只有一个结点也可以。**n1，n3为空

最初的判断也可以写成这样：

    //只有一个结点/链表为空，不用反转
   if(head == NULL || head ->next == NULL)
   {
       return head;
   }

方法3：头插法-头指针

==方法：==

• 创建一个头指针，把原来链表的结点头插到头指针中

还要定义两个指针：cur :标志要头插的结点 ，next :保存下一个结点

步骤：

• 1.定义一个结构体指针当成头指针

• 2.保存下一个结点，不然头插到新链表之后就找不到了：next = cur->next

  • 把链表的结点头插到头指针中(cur->next = newhead)，然后自己成为新的头(head = cur) (注意：要保存下一个结点，不然找不到了) ，

  • 然后把下一个结点赋给cur(cur = next)， 不断迭代

  • cur：标志要头插的结点 next：保存cur的下一个结点

  • 迭代结束条件：cur为空(即把所有结点都头插了)

• 最后newhead就是反转链表后的头

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    /* 此处也可以不判断
   if(head == NULL)
   {
       return NULL;
   }
   */
    //因为如果head为空，cur为空，不进入循环，返回newhead为空
    
    struct ListNode* cur = head; //要头插的结点
    struct ListNode* next = NULL;   //保存下一个结点
    struct ListNode* newhead = NULL;    //头指针
    //cur为空结束循环
    while(cur)
    {
        //保存下一个结点
        next = cur->next;
        //头插
        cur->next = newhead;
        //插入的结点成为新的头
        newhead = cur;
        //迭代往后走
        cur = next;
    }
    return newhead;
}