seo对网站优化,广州信科做网站,推广公众号,网站建设工作分工文章目录 前言方法一#xff1a;构造新链表#xff08;构造新节点#xff09;方法二#xff1a;构造新链表#xff08;不构造新节点#xff09;方法三#xff1a;递归方法四#xff1a;双指针方法五#xff1a;遍历总结 力扣题目链接#xff1a;206. 反转链表 牛客题… 文章目录 前言方法一构造新链表构造新节点方法二构造新链表不构造新节点方法三递归方法四双指针方法五遍历总结 力扣题目链接206. 反转链表 牛客题目链接BM1 反转链表
前言 反转链表作为链表操作的基础是重中之重以后做比较难的链表题目也可能会需要嵌入反转链表的代码所以一定要多多练习 方法一构造新链表构造新节点 思路构造一个新的链表从旧链表依次拿到每个节点根据旧链表创建新节点添加至新链表头部完成后新链表是倒序的 public ListNode reverseList (ListNode head) {//新链表的头节点还没有元素定义为nullListNode n1 null; //设置一个指针用来遍历旧链表ListNode p head;//循环遍历旧链表while(p ! null){//根据旧链表的值创建新节点把新节点的next指针设置为新链表的头节点并更新新链表的头节点n1 new ListNode(p.val,n1);p p.next;}//返回新链表的头节点return n1;
}方法二构造新链表不构造新节点 与方法一类似构造一个新链表从旧链表头部移除节点添加到新链表头部完成后新链表是倒序的————是不是看完后很蒙和方法一一样啊方法一是根据旧链表的值构造节点方法二是直接使用旧链表的节点没有创建新的节点 public ListNode reverseList (ListNode head) {ListNode p1 head;ListNode p2 null;while(true){//记录旧链表的头指针ListNode first head;//如果旧链表的指针指向null就退出循环if(first null){break;}//旧链表向前一步head head.next;//将旧链表的头指针指向新链表的头first.next p2;//更新新链表的头指针p2 first;}return p2;
}方法三递归 递归找到并返回最后一个节点记录为新节点从倒数第二个开始将后一个节点的指针指向自己也就是p.next.next p)再将自己的next指向null避免死循环 public ListNode reverseList(ListNode head) {//递归结束条件和链表为空的条件判断if(head null || head.next null){return head;}//递归调用当递归到最后一个节点时返回也就是反转后的头节点我们用变量记录下来ListNode newHead reverseList(head.next);//从倒数第二个节点开始将后一个节点的指针指向自己head.next.next head;//将自己的next指针指向null避免死循环head.next null;//返回头节点return newHead;
}方法四双指针 双指针法定义两个指针都先指向头节点。将旧链表指针的下一个节点断开插入到链表的头节点处更新新链表的指针 public ListNode reverseList(ListNode head) {//判断链表为空的情况if(head null){return head;}//定义新链表指针ListNode n1 head;//定义旧链表指针ListNode o1 head;//判断条件旧链表指针的下一个节点不为nullwhile(o1.next ! null){//记录旧链表的下一个指针ListNode temp o1.next;//跳过旧链表指针的下一个节点o1.next o1.next.next;//将跳过的指针指向头temp.next n1;//更新新链表的指针n1 temp;}return n1;}方法五遍历 遍历法定义三个指针从前向后遍历一遍并更改指针的指向 public ListNode reverseList(ListNode head) {//前指针ListNode prev null;//当前指针ListNode p head;//后一个指针ListNode next null;while(p ! null){//后一个指针为什么要在循环里面赋值呢避免head为null的情况next p.next;//将当前指针指向前一个p.next prev;//更新前指针prev p;//更新当前指针p next;}//这里为什么要返回前指针因为p在循环里面被更新为null循环才不能进行所以循环走完后prev的位置是头节点的位置return prev;}总结 本文讲解了反转指针的五种方法反转指针是链表操作中的基础但是特别重要大家快去练习把~
