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

4

我的小站——半生瓜の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,
迭代往后走,取下一个结点......
**代码实现:**
```c
/**
 * 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;
}