【原】3分钟学个算法：链表反转

艾小仙 2022-07-13 发布于上海

展开全文

题目描述

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

输入

{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的元素位置进行对调进行实现。集合原理图如下：

集合反转代码实现如下：

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指针指向当前遍历节点。直接改变当前指针的指向，由指向下一个节点改造为指向前面的节点。原理图如下：

代码实现如下：

  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特性用分别用addLast与pollLast方法进行添加和删除，反转集合后重建指针指向，这类思路，时间复杂度是O(n)，空间复杂度是O(n)（因为创建新的列表需要空间，栈也同样需要），针对链表反转总体效率不如第一种。

-----------分割线-----------

说点题外话，我还在想个slogan，看别人结尾都带句话就觉得很吊的样子，看看别人。