力扣每日一道系列 --- LeetCode 206. 反转链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣每日一道系列 --- LeetCode 206. 反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣每日一道系列 --- LeetCode 206. 反转链表,LeetCode每日一道,leetcode,链表,算法

📷 江池俊：个人主页 🔥个人专栏： ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人，再渺小也不会迷途。

LeetCode 206. 反转链表

力扣每日一道系列 --- LeetCode 206. 反转链表,LeetCode每日一道,leetcode,链表,算法

思路一：头插

初始化两个指针，cur 和 newhead。cur 指向给定的链表头节点，newhead 初始为 NULL。

在 cur 不为空的情况下，执行循环。

首先，记录下 cur 的下一个节点 next。

然后，将 cur 的 next 指针指向 newhead，实现当前节点 cur 逆序接入新链表。

接着，将 newhead 指向 cur，以便下一次循环时，newhead 就能指向新链表的下一个节点。

最后，将 cur 移动到下一个节点。

当 cur 为空时，说明已经遍历完整个链表，此时 newhead 就是反转后的链表头，返回 newhead。

头插法的好处是无需遍历链表就可以直接修改指针关系，实现反转。时间复杂度为 O(n)，空间复杂度为 O(1)。

 //头插法
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;

    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

思路二：原地改变节点指向

定义三个指针 n1、n2 和 n3。n1 初始为 NULL，n2 初始指向链表头节点，n3 初始为 n2 的下一个节点。

使用 while 循环，遍历链表。在每次循环中，做以下操作：

将 n2 的 next 指针指向 n1，实现 n2 节点的指向反转。

将 n1、n2 和 n3 分别向后移动一个节点。具体地，将 n1 指向 n2，将 n2 指向 n3，将 n3 指向 n3 的下一个节点。

当 n2 为空时，说明已经遍历完整个链表，此时 n1 就是反转后的链表头，返回 n1。

这个算法的优点是只需要遍历一次链表就能完成反转操作，时间复杂度为 O(n)，空间复杂度为 O(1)。文章来源地址https://www.toymoban.com/news/detail-756925.html

 //原地改变节点的指向
  struct ListNode* reverseList(struct ListNode* head) {
      if(head==NULL)
      {
          return NULL;
      }
      struct ListNode* n1 = NULL;
      struct ListNode* n2 = head;
      struct ListNode* n3 = n2->next;

      while(n2)
      {
          n2->next = n1;

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