一起刷 leetcode 之反转链表

题目

这道题是 leetcode 的 206 题

给定一个链表，然后将其反转后输出

例如：

输入：1->2->3->4->5->null

输出：5->4->3->2->1->null

对应的题目链接 反转链表

解析

这道题的难度属于简单，思想挺简单，但想写对也不是很容易

我这里给出的方法是迭代法

遍历链表，将当前节点的 next 指针改成指向前一个元素，这里需要提前存储前一个元素。在更改引用前，先获取下一个节点，然后把 pre 和 cur 都前进一步，最后返回新的头节点

时间复杂度：O(n)

空间复杂度：O(1)

  

   

    

     

    
    

     

      public ListNode reverseList(ListNode head) {
     
    
   

    

     

    
    

     

              ListNode pre = 
      null;
     
    
   

    

     

    
    

     

              ListNode cur = head;
     
    
   

    

     

    
    

     
        
      while (cur != 
      null) {
     
    
   

    

     

    
    

     
            
      // 记录当前节点的下一个节点
     
    
   

    

     

    
    

     

                  ListNode temp = cur.next;
     
    
   

    

     

    
    

     
            
      // 将当前节点指向 pre
     
    
   

    

     

    
    

     

                  cur.next = pre;
     
    
   

    

     

    
    

     
            
      // pre 和 cur 都前进一步
     
    
   

    

     

    
    

     

                  pre = cur;
     
    
   

    

     

    
    

     

                  cur = temp;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        
      return pre;
     
    
   

    

     

    
    

     

          }