第18个题-反转一个单链表

这是整理的第18个题。

学会分析一个就足够了
累计记录

类似题目

链表为了 完成o(1)插入，需要定义2个节点
head，tail 目前这是标准2个方式。
这个是不会发生变化的。--需要一个头节点

• 链表插入排序
• 部分反转
  vs

--------------------开始------------------------

leetcode-206 反转一个单链表。

reverse-linked-list
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

方法一 ：迭代（链表前插）

• 分析
  也许你做过很多遍了，
  但是真正发现里面变化规律。
  发现以前认识不到地方

这是一个基本题目，考察绘制过程图
观察规律

描述：

1. 假设链表第一个节点 就是最后最后一个节点 end（最后一个节点如何表示为head呢），end始终保持不变
2. 最后一个节点 end 需要指向 end.next.next ,因为end.next 插入head后面
3. 在遍历过程中，变化的start节点
   用头节点来固定

• code

class Solution {
public:
    /**
    Reverse a singly linked list.
    Example:
    Input: 1->2->3->4->5->NULL
    Output:5->4->3->2->1->NULL
    
    演示 第一节点 如何变成最后一个节点的
          end cur
           |  |  
           |  |
    start->1->2->3->4->5->NULL (初始化)
    
         
         (3) (2) (1)  发送了3个变化
    start: 2 ->1->3->4->5->NULL  (反转1次后仍然是完整链表)  
              |  |
              |  |
             end cur
    
    （3）（2）     （1）
    start: 3 ->2 ->1->4->5->NULL  (反转2次后仍然是完整链表)  
                   |  |
                   |  |
                   end cur  
    理解偏差
    1 结合反转2考虑一下，这是一个链表，不是去构造另外一反转前的链表和反转后的链表，主要上学记住了构造新的链表。理解偏差1
    2 理解偏差2 虽然知道反转第一个节点，变成最后一个阶段，但是根本理解有什么用
      开始之后1--2
      最后一个1--NUll
      循环做好准备 
    3 有没有造成死循环 1 --NULL 产生方式。理解有点模糊 ，还是判断cur是否为null
    
    4.理解偏差3 
     默认第一个节点是返回第一节点也是最后一个节点，这里无法区分 1->next 含义是开始还end的操作
     1->next 是怎么变化的
      
     复杂度分析

    时间复杂度：O(n)
    空间复杂度：O(1)
         
    **/
    ListNode* reverseList(ListNode* head) 
    {
     
     ListNode start(-1);
     start.next=head;//保证 start 一定存在，才可以执行start.next
     
     ListNode* end=head;//默认第一个节点是翻转链表最后一个节点
     
     ListNode* cur=NULL;
     while(end &&end->next)
     {
         cur=end->next;
         end->next=cur->next;//(1) 1--4
         cur->next=start.next;//(2) 3-2-1
         start.next=cur;//(3) // 3-2-1-5
         
     }
     
     return start.next;
     
    }
    
    
};

• 复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

方法二：递归（链表后插）

递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？

逻辑

• code

/**
   head head.next
input： 1-->2-->3-->4-->5-nill

                      (head)     
第一次：1-->2-->3 ---4-NUll
                     5-->4--NUll
3和5都指向节点4 
                 
第二次：1-->2-->3

         5-->4-3-NULL
        
last次：5-->4-3-2->1NULL
**/
func reverseList(head *ListNode) *ListNode {
    if head ==nil ||head.Next==nil {
      return head //最后一个节点返回，head==nil为防止输入的为nill
    }
    
    first:=reverseList(head.Next)
    
    head.Next.Next=head //第k个节点放到第k+1后面
    head.Next=nil
    
    return first
}

• 复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)
由于使用递归，将会使用隐式栈空间。