LeetCode刷题(1)【链表】【反转链表】(C语言)

我的小站——半生瓜のblog (doraemon2.xyz)

题目链接——206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

反转链表

思路一:反转指针。

本质上就是调转指针的方向。

首先我们定义两个指针,一个叫n1，一个叫n2。(Node1,Node2)

让n2指向第一个结点，让n1指向空。

n2->next指向n1。

但是，两个指针是反不转的。因为：

这里让n2->next指向n1，就是把n1的值存到n2的next上，n2->next原来存的是2的地址，现在存的是NULL，但是继续往后走的时候，我们发现找不到2了 。

所以要反转指针，两个指针是反不动的，要用3个。

前两个指针 反转，最后一个指针负责记录下一个位置。

什么时候结束

n2 == NULL；

重复的条件用循环解决

1. 初始条件
2. 迭代过程
3. 结束条件
   画图看起来很浪费时间，但提升了写代码的体验，更好的解决问题。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

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 = n3->next;
        }
    }
    return n1;
}

思路二：头插法
取结点头插到新链表中。cur是当前操作结点，用一个next来保存下一个结点(同上)。
文字简单描述：
​ 从原链表去一个点下来，放到新的链表中，当做新链表的头结点cur = newhead,
迭代往后走，取下一个结点…
代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
   struct ListNode* cur = head;
   struct ListNode* newHead = NULL;
   while(cur != NULL)
   {
       struct ListNode* next = cur->next;
        //头插法
        cur->next =newHead;
        newHead = cur;
        cur = next;
   }
   return newHead;
}