leetcode第206题反转链表?

发布时间:2024年01月03日

一:题目:

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

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

二:解题思路

?这道题我们可以用迭代或递归地反转链表。但是这个题更加适合迭代的方法去做。所以我们应该有的一个思维是三个指针立方向。?

首先,我们要设置三个变量(这里的变量不要随便设,我们可以从前到后设置n1,n2,n3)

反转链表我们只需要两个就行了,但是我们就找不到3了所以需要第三个变量,例如下面的图片

但是仅仅分析到这里还是不够的,我们需要将新的next指向NULL,所以我们需要将n1赋值为NULL,n2赋值为1,n3赋值为2,然后就可以进行反转,但是还是有一个问题,就是什么时候结束,我们可以依次反转下去会发现当n2为NULL时就结束了。(上述讲述均以下面的图片为依据)

那么这道题就分析完了。

?三:解题代码

首先,我们要想如果这个链表只有一个数,甚至没有是空的,那就没有解题的意义了,所以我们需要先判断这个链表


    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;
     if(n3) 这里是为了防止当n2到达NULL时,下一步发生空指针异常。
     n3=n3->next;
   }
    return n1;这里的n1为链表头所以返回n1

完整代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *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;
     if(n3)
     n3=n3->next;
   }
    return n1;
}

文章来源:https://blog.csdn.net/2302_79282659/article/details/135355844
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。