当前位置：首页 > article >正文

OJ06：206.反转链表

article 2024/11/9 6:09:41

题目

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

示例：
在这里插入图片描述

我们假设是这样的一个链表：

struct ListNode {
    int val;
    struct ListNode* next;
};

方案一：迭代

思路分析

定义3个链表指针：
❤struct ListNode* n1 = NULL,* n2 = head, * n3 = head->next;

我们通过循环迭代的方式来将其原地反转：
反转：

❤n2->next = n1;

迭代：

//迭代
❤ n1 = n2;
❤ n2 = n3;
//防止最后的引用NULL
if (n3 != NULL)
{
n3 = n3->next;
}

在这里插入图片描述

代码展示

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* n1 = NULL, * n2 = head, * n3 = head->next;
    while (n2)
    {
        //反转
        n2->next = n1;
        
            //迭代
            n1 = n2;
            n2 = n3;
            //防止最后的引用NULL
            if (n3 != NULL)
            {
                n3 = n3->next;
            }
    }
    return n1;
}

方案二：递归

这种方法理解起来有点困难：
比较难以表达，这里展示一下代码：

struct ListNode* Reverse(struct ListNode* head) {
    struct ListNode* pre = NULL;
    if (head == NULL || head->next == NULL)   //空链表或只有一个节点的链表直接返回头指针
    {
        return head;
    }
    struct ListNode* newHead = Reverse(head->next);    //进行递归，找到最后一个节点后返回
    head->next->next = head; //把当前节点的下一个节点指针指向这个节点，不断归，实现链表的反转
    head->next = NULL;
    return newHead;//最后返回新的头结点
}
}