【C语言】Leetcode 206.反转链表

题目

解决思路

思路一：翻转链表

struct ListNode* reverseList(struct ListNode* head) 
{
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* n1 = NULL,*n2 = head,*n3 = n2 -> next;
    while(n2 != NULL)
    {
        n2 -> next = n1;
        n1 = n2;
        n2 = n3;
        if(n3 != NULL)
        {
            n3 = n2 -> next;
        }
    }
    return n1;
}

我们定义三个节点的指针n1，n2，n3.分别指向NULL，head，head -> next。这样我们通过三个指针来临时存放各个节点，以此为基础来重新将各个节点进行链接。之后通过while循环使指针向后移动，逐一将n2位置的节点断开与n1之前的链接，再由n2指向n1进行链接。

过程如下图：

思路二：头插法

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;
}

首先我们定义了两个结构体指针，cur和newhead，用cur来指向当前的节点，从head开始；用newhead指向一个NULL，newhead将作为后面链接新链表的表头。

然后我们用while循环将链表遍历，直到cur的指向是NULL。在遍历的过程中，每一次cur指向的节点不是NULL的时候定义一个结构体指针next，该指针用来暂时保存cur的next，因为在连接的时候cur会先被用来去链接在新链表上，这样的话就没法找到之前链表中cur指向的下一个节点了，所以用next指向下一个节点来保证完成整体的链表的遍历。

在保证可以正常完成遍历后，我们就可以来实现每一层循环的逻辑了：

cur的next指向newhead实现了以下操作：

newhead指向cur实现了以下操作：

cur指向next实现了以下操作：

通过以上的逻辑，在一层层遍历后，直到cur对应的节点为空的时候也就表示原来的节点已经被全部链接到新的链表上了，完成了链表的反转。

以上就是该篇的全部内容啦~

如果我的博客对您的学习有帮助，希望可以得到您的三连~