【算法】反转链表的四种方法（C语言）

文章目录

• 方法一 原地反转
• 方法二 迭代
• 方法三 递归
• 方法四 新建链表法

  206. 反转链表

  给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  示例 1：

  

  输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

  示例 2：

  

  输入：head = [1,2] 输出：[2,1]

  示例 3：

  输入：head = [] 输出：[]

  提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 next:1.连:第一步先将pre所在节点和cur->next所在节点连接起来,将当前节点 cur 从链表中移除，并把链表连接起来。

    

    cur->next = head;2.掉:将cur的next指向head，将cur插入到head的前面,以便将其放置到链表的前面，成为新的头节点。

    head = cur;3.接:更新head，使其指向当前的cur

    

    cur = pre->next;4.移:更新cur，移动到下一个待反转的节点

    

    struct ListNode* reverseList(struct ListNode* head) {
        if (head == NULL) {
            return head;
        }
        struct ListNode* cur = head->next; 
        struct ListNode* pre = head; 
        while (cur) {
            pre->next = cur->next; 
            cur->next = head; 
            head = cur;   
            cur = pre->next; 
        }
        return head; 
    }
    

    方法二 迭代

    temp保存cur的下一个节点，以防止反转时丢失链表信息。

    

    cur->next = pre;将cur的下一个指针指向pre,实现反转。

    

    更新pre为当前的cur,为下一次迭代做准备。

    更新cur为保存的下一个节点temp,继续迭代。

    

    通过不断改变指针的指向将链表进行反转。pre充当新链表的头节点,当cur为NULL循环停止，返回pre

    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* pre = NULL;
        struct ListNode* cur = head;
        while (cur != NULL) {
            struct ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    

    方法三 递归

    我们可以通过迭代的方法来得到递归方法

    观察reverse函数，

    函数声明中pre指针指向的为NULL，cur指针指向的为head，正如递归中声明并初始化的pre和cur指针

    递归结束条件为cur为NULL,返回pre

    同样temp保存cur的下一个节点，以防止反转时丢失链表信息。

    然后进行反转cur->next = pre;

    pre 为当前已反转部分的头节点，cur为当前待反转的节点。

    然后调用递归，将cur作为新的pre传入下一层，将temp作为新的cur传入下一层。

    实现了链表的递归反转

    struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) {
        if (!cur){
            return pre;
        }
        struct ListNode* temp = cur->next;
        cur->next = pre;
        //将cur作为pre传入下一层
        //将temp作为cur传入下一层，改变其指针指向当前cur
        return reverse(cur, temp);
    }
    struct ListNode* reverseList(struct ListNode* head) {
        return reverse(NULL, head);
    }
    

    方法四 新建链表法

    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

    newNode->val = head->val;

    新建一个链表，并初始化

    newNode->next = newHead;将新节点插入到新链表的头部

    

    newHead = newNode;

    

    head = head->next;

    

    遍历原链表，使用头插法新建链表，并不断移动newHead指针，当原链表头指针指向NULL最终返回newHead

    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* newHead = NULL;
        while (head) {
            // 创建一个新节点
            struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
            newNode->val = head->val;        
            // 将新节点插入到新链表的头部
            newNode->next = newHead;
            newHead = newNode;
            // 移动到原链表的下一个节点
            head = head->next;
        }
        return newHead;
    }
    

    ---

    ---

    感谢您的阅读