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

在这里插入图片描述

📷 江池俊：
个人主页

🔥个人专栏：
✅数据结构探索
✅LeetCode每日一道

🌅 有航道的人，再渺小也不会迷途。

LeetCode 206. 反转链表

在这里插入图片描述

思路一：头插

初始化两个指针，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)。

 //原地改变节点的指向
  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;
  }

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/968cbaf519.html

力扣每日一道系列 — LeetCode 206. 反转链表

思路一：头插

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

相关推荐