开发者社区> 1560195324766884> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

3分钟学个算法:链表反转

简介: 3分钟学个算法:链表反转
+关注继续查看

题目描述


输入一个链表,反转链表后,输出新链表的表头。


输入

{1,2,3,4,5}

返回值

{5,4,3,2,1}

解题


初拿到这题,很容易联想到反转系列用java的api中提供了几个类似的api如Collections.reverse()StringBuilder.reverse()。他们提供了直接对集合、字符串的反转api。需要的就是根据链表构建集合,再将集合反转,反转后再重新构建链表指向关系。

代码如下:

public static ListNode reverseByList(ListNode head) {
        //方法先判断入参
        if (head == null) {
            return null;
        }
        //只有一个元素的直接返回
        if (head.next == null) {
            return head;
        }
        List<ListNode>  list=new ArrayList<>();
        while(head!=null){
            list.add(head);
            head=head.next;
        }
        //直接使用Collections的reverse反转
        Collections.reverse(list);
        // 反转后重建指向关系
        for(int i=0;i<list.size()-1;i++){
            list.get(i).next=list.get(i+1);
        }
        //链表最后一元素的next置为空
        list.get(list.size()-1).next=null;
        return list.get(0);

    }

上面的方法确实能解决问题,但是一般出到这题,考的不会是你的api的熟练程度,面试官一般会要求你自己实现反转过程。对于集合的反转,自己实现的通用算法是index为i的和index为size-1-i的元素位置进行对调进行实现。集合原理图如下:

bf1d45bf6d2cfed1a275b0a29a14e3de.jpg

集合反转代码实现如下:

public static void reverseList(List<ListNode> list){
         // 如果只有0或者1个元素,不需要做处理
         if(list.size()<=1){
             return;
         }
         int size=list.size();
         int half=(size-1)>>1;
      //从中号位遍历到0号位,将i位与size-1-i位进行互换实现集合的反转
         for(int i=half;i>=0;i--){
             ListNode temp=list.get(size-1-i);
             list.set(size-1-i,list.get(i));
             list.set(i,temp);
         }
     }

对于链表反转,上面链表反转思路是转为集合,对集合进行互换位置反转,然后再重建指针指向。还有一种只针对链表反转更有效的方式,即直接改变指针指向即可。用一个pre保持指向之前的节点的指针,用一个current指针指向当前遍历节点。直接改变当前指针的指向,由指向下一个节点改造为指向前面的节点。原理图如下:

f57eb2b9a4d1e78194cc80184aec65ba.jpg

代码实现如下:

  public static ListNode reverseLinkNode(ListNode head) {
          //方法先判断入参
          if (head == null) {
              return null;
          }
          //只有一个元素的直接返回
          if (head.next == null) {
              return head;
          }
      // 用于保持之前的指针,便于current指向
          ListNode pre = null;
          ListNode current = head;
          //temp用于保持当前节点的下一个节点的指针,使得遍历继续
          ListNode temp;
          while (current != null) {
              temp = current.next;
              current.next = pre;
              pre = current;
              current = temp;
          }
          //因为循环终止条件是到最后current为null了,链表的头节点应该是pre,即最后一个非空节点
          return pre;
      }

还有没有其他思路?在集合反转的时候除了交换对称位置的元素,如果想到 stack 的 FILO 特性,也很方面的使用 stack 进行反转集合,但是要额外使用一个n大小的栈空间。时间复杂度都是O(n)。java中需要用栈可以用LinkedList实现。


总结


对于链表反转主要两种思路:


一个是直接改变链表节点指针实现,即原先指向下一个节点的指针改为指向前一个节点,这种时间复杂度是O(n),空间复杂度是O(1),一次遍历完成,效率较高。


另一种即将链表转为集合,可以用Java的Collections.reverse()直接反转或者用交换头尾元素的思路或者利用LinkedList的 FILO特性用分别用addLastpollLast方法进行添加和删除,反转集合后重建指针指向,这类思路,时间复杂度是O(n),空间复杂度是O(n)(因为创建新的列表需要空间,栈也同样需要),针对链表反转总体效率不如第一种。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
重温算法之排序链表
这个题目有点麻烦,如果是使用的暴力法,会直接超时,使用自顶向下的归并排序的话,其实也没有多大的提升,目前是没有好的解决方案的,后期继续思考吧。
20 0
【链表面试题:腾讯】反转链表
【链表面试题:腾讯】反转链表
31 0
翻转链表算法和实现
1 翻转思路 1-1 整体的思路 1-2 详细的思路 2 代码实现 3 运行结果 写个翻转链表算法,刚开始想到一个不错的思路。这个思路运行效率不低,时间复杂度为O(n);可以不用分配额外的节点空间,空间复杂度为O(0)。
1272 0
RSA算法加解密示例
RSA加密与解密 RSA算法的密钥由公钥和私钥组成,公钥用于加密,私钥用于解密。顾名思义,公钥就是可以进行公开的密钥,一般可以公开给你的合作伙伴;私钥就是私有的,也就是只有你知道的,你的合作伙伴通过你提供的公钥进行加密的内容只有你能进行解密,这样也就只有你知道他发的是什么内容。
916 0
一步一步写算法(之单向链表)
原文: 一步一步写算法(之单向链表) 【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】     有的时候,处于内存中的数据并不是连续的。
598 0
【算法导论】链表队列
        链表队列很简单,之前看到过,没有用程序实现。其原理就是遵循FIFO原则,只能从队首取元素,从队尾插入元素,就和排队模型一样。因此只需要队首指针和队尾指针就可以方便的进行队列操作。
848 0
64
文章
0
问答
文章排行榜
最热
最新