[206]. 反转链表(C语言)

一时失言乱红尘 2022-12-29 06:37 91阅读 0赞

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/reverse-linked-list][https_leetcode-cn.com_problems_reverse-linked-list]

# 思路1：迭代 #

![在这里插入图片描述][2020122020504846.png]

> 设置三个指针，prev，cur和next分别指向当前节点的前一个结点、当前节点和当前节点的后一个节点  
> 初始化prev置空，开始遍历链表，反转链表四步走：

*  第一步，将cur->next指向prev
 *  第二步，prev指向cur
 *  第三步，cur指向next
 *  第四步，next指向next->next  
    ![在这里插入图片描述][20201220210447848.png]  
    **注意**：

> 遍历链表结束条件为cur当前节点为空，如上图所示，当cur->val为5时，next为NULL，==当cur后移指向NULL时，next早已为NULL，next->next会发生报错！==有两种写法避免

# 代码1： #

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    typedef struct ListNode Node;
    struct ListNode* reverseList(struct ListNode* head){
        
        if(NULL == head)
        {
        
            return head;
        }
        Node * prev=NULL;
        Node * cur=head;
        Node * next=head->next;    
        while(cur!=NULL)
        {
        
            
            cur->next=prev; //当前节点指向前一个节点
            prev=cur;   //prev后移
            cur=next;   //cur后移
    
            //1.next不为空时继续后移
            if(next) 
            {
        
                next=next->next;
            }
        }
    
        return prev;
    }

# 代码2： #

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    typedef struct ListNode Node;
    struct ListNode* reverseList(struct ListNode* head){
        
        if(NULL == head)
        {
        
            return head;
        }
    
        Node * prev=NULL;
        Node * cur=head;
        while(cur!=NULL)
        {
        
            Node * next=cur->next; //每次循环定义next指向cur后的一个节点
            cur->next=prev; //当前节点指向前一个节点
            prev=cur;   //prev后移
            cur=next;   //cur后移
        }
    
        return prev;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

# 思路2：递归 #

![在这里插入图片描述][d1d93ba4cc7afe1a2073443ffeb96350.gif_pic_center]  
递归的思想就是将一个大的问题划分成一个个小的问题，而这些小问题与大的问题具有相同的解决思路，通常递归的代码简洁，但却难以理解。

> 本题算法可以将链表划分为：
> 
>  *  一个节点和其它已逆置节点
>     
>      *  一个节点和其它已逆置节点
>         
>          *  一个节点和其它已逆置节点
>             
>              *  …

这样就可以把这个问题看成解决一个节点和其它已经逆置节点的问题，使用递归需要两个条件

> 1.递归出口，即递归结束条件  
> **显然结束条件为当前节点为空时直接返回**  
> 2.寻找解决最小问题的等价关系，  
> 原链表1->2->3->4->5,假设递归到最后一个节点1，而其他节点2345已经逆置，即1->2<-3<-4<-5,如图  
> ![在这里插入图片描述][20201221165518753.png]
> 
>  *  第一步首先让head->next的next指向1就可以了，即head->next->next=head，链表变为5->4->3->2->1  
>     第二步将头节点的next置空，即head->next=NULL  
>     ![在这里插入图片描述][20201221170058930.png]

# 代码 #

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    typedef struct ListNode Node;
    struct ListNode* reverseList(struct ListNode* head){
        
        /* 思路2 递归*/
        //结束条件
        if (NULL==head || NULL == head->next)
        {
        
            return head;
        }
    
        Node * ret=reverseList(head->next);    //迭代
        head->next->next = head;
        head->next=NULL;
        return ret;
    
    }

[https_leetcode-cn.com_problems_reverse-linked-list]: https://leetcode-cn.com/problems/reverse-linked-list
[2020122020504846.png]: /images/20221120/b08e0fc040384c94b4428d7f1d4b4a4c.png
[20201220210447848.png]: https://img-blog.csdnimg.cn/20201220210447848.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020122021145050.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy,size_16,color_FFFFFF,t_70
[d1d93ba4cc7afe1a2073443ffeb96350.gif_pic_center]: https://img-blog.csdnimg.cn/img_convert/d1d93ba4cc7afe1a2073443ffeb96350.gif#pic_center
[20201221165518753.png]: https://img-blog.csdnimg.cn/20201221165518753.png
[20201221170058930.png]: https://img-blog.csdnimg.cn/20201221170058930.png