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

LeetCode 206. 反转链表

思路一：头插

1. 初始化两个指针，cur 和 newhead。cur 指向给定的链表头节点，newhead 初始为 NULL。
2. 在 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;
}

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

1. 定义三个指针 n1、n2 和 n3。n1 初始为 NULL，n2 初始指向链表头节点，n3 初始为 n2 的下一个节点。
2. 使用 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;
  }