0


[ 链表OJ题 2 ] 反转链表

题目来源:

  1. 反转链表 - 力扣(LeetCode) (leetcode-cn.com)

题目描述:

代码实现:

1、方法一:

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

1.1思路分析:

我们要让原链表逆置,我们可以让箭头反过来,再把head指向尾结点即可。

因此我们可以创建3个变量n1,n2,n3;其中n1置空,用来让头结点的next指向空,让n2赋值为head,n3用来保存n2的next节点,其中n3的创建是必须的,因为当箭头逆置时,n2的next指向了n1,就无法找到原链表中n2的next节点,而且原链表中n2的next节点有且仅有n2可以找到,因此,n3的作用就是保存原链表中n2的next节点。

其中:

1、当原链表为空时,需要直接返回NULL;

2、n2->next = n1,n1=n2,n2= n3,n3 = n3->next。这是循环向后走的赋值,顺序不能错,我们可以发现,什么时候停止-->经过分析可以看到只要n2不为空,我们就还要向后走,因此循环的条件为n2!=NULL;

3、因题目要求返回头节点,因此我们只需要返回n1即可。return n1;

4、在上述循环中,我们移动n3是通过n3找n3的next,但是当我们到最后一次时,n3已经为空,如果我们再让n3 = n3->next,会出现空指针异常,因此我们必须加上判断条件,并且在最后一次中,n3即使不再向后移动,原链表也会翻转,因为无序再向后走了。

2、方法二:

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

2.1思路分析

头插法:

我们要达到逆置原链表,我们可以选择使用头插法。

我们创建一个新的头newhead,让newhead置为NULL,在创建一个cur指针指向原来的head,创建next指针用来保存cur的下一个指针。这个next节点也是必须创建的,原因是cur的next指向newhead后无法找到原链表中cur的next节点,因此我们必须让next保存这个节点。

其中:

1、我们让cur的next指向newhead,再让newhead指向cur,cur指向next,next指向next的下一个节点。顺序一定不能乱。循环停止的条件为,cur只要不为空,就可以一直头插,知道cur为空。

2、题目要求返回新的头结点,因此我们只需要返回newhead即可。

3、此方法我们无序考虑原链表是否为空,因为我们创建的newhead为NULL,如果原链表为空,即cur一开始就是空,不会进入到循环条件里面,直接return newhead,因此无需判断。

(本题完)

标签: c语言 数据结构

本文转载自: https://blog.csdn.net/qq_58325487/article/details/123597900
版权归原作者 小白又菜 所有, 如有侵权,请联系我们删除。

“[ 链表OJ题 2 ] 反转链表”的评论:

还没有评论