2._反转链表

• 2.10

  • 尾插法依旧忘记了返回的是 pre
  • 递归法：终止条件先判断当前是不是空链表，在判断 head。next！=null，找到最后的节点

• 1.24

  • 两个方法都做了一遍，尾插法返回的是 pre

• 1.18

  • 绷不住了，想到了递归，递归需要返回新的head 头啊，不用哨兵节点

• 法 3：递归法（学树学习惯了）

class Solution {
    public ListNode reverseList(ListNode head) {
        
        return reverse(head);
    }
    public ListNode reverse(ListNode node){
        if(node==null||node.next==null) return node;
        ListNode newHead = reverse(node.next);
 
        node.next.next=node;
        node.next=null;
        return newHead;
    }
}

• 法1:额外数组

class Solution {
    public ListNode reverseList(ListNode head) {
        int temp = 1;
        int i = 0;
        ListNode link= head;
        List<Integer> results = new ArrayList<>();
        while(link!=null){
            temp =  link.val;
            results.add(temp);
            link = link.next;
        }
        Collections.reverse(results);
        ListNode newLink = new ListNode(0);
        link = newLink;
        for(int result:results){
            link.next = new ListNode(result);
            link=link.next;
        }
        return newLink.next;
 
    }
}

• 法2:当场反转(迭代法?)

 
1(pre)(null)-》2(current)-〉3(temp)
 
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre =null;
        ListNode currt = head;
        while(currt!=null){
            ListNode temp = currt.next;
            // currt= next;先更新链条在迁移节点
            currt.next = pre;
            pre=currt;
            
            currt=temp;
 
        }
        return pre;
}}

 
			ListNode temp = current;
            current.next = pre;
            pre = current;
            current = temp.next;
            //这一版本中,先砍断了curent与后面的节点,保存的是curent本身,后面current = temp.next;时就是pre,而不是真正的current后面的3