01-反转链表

问题描述

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

解答思路

public class LinkedReverse {  
  
    public static class ListNode{  
        int val;  
        ListNode next;  
        ListNode() {}  
        ListNode(int val) { this.val = val; }  
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }  
        public static ListNode getListNode(){  
            ListNode node5 = new ListNode(5, null);  
            ListNode node4 = new ListNode(4,node5);  
            ListNode node3 = new ListNode(3,node4);  
            ListNode node2 = new ListNode(2,node3);  
            return new ListNode(1,node2);  
        }  
    }  
  
    public static void main(String[] args) {  
        ListNode head = ListNode.getListNode();  
        head = reverseListTwo(head);  
        while (head != null){  
            System.out.println(head.val);  
            head = head.next;  
        }  
  
    }  
    // 迭代方式： 方法返回的反转后的头指针  
    public static ListNode reverseList(ListNode head) {  
        ListNode prev = null;  
        ListNode curr = head;  
        while (curr != null) {  
            // 将next指向前一个节点之前，先保存后面的数据不然 就丢失了  
            ListNode newCurr = curr.next;  
            // 将next指向前一个节点  
            curr.next = prev;  
            // pre和curr 后移一位  
            prev = curr;  
            curr =  newCurr;  
        }  
        return prev;  
    }  
    // 递归方式： 方法返回的反转后的头指针  
    public static ListNode reverseListTwo(ListNode head) {  
        // head == null 表示 链表是null的;  head.next == null 表示已经处理到最后一个节点了  
        if(head == null || head.next == null){  
            // 最一个节点  
          return head;  
        }  
        // 不管head 是几返回的都是 最一个节点 目的就是将头暴露出去  
        ListNode newHead = reverseListTwo(head.next);  
        // 当head=4开始 迭代执行  因为head.next = 5 所以head.next.next = 5.next，5.next = head就是将5指向4  
        head.next.next = head;  
        // head.next = null表示将 4指向5的链接断了，防止环形链表  
        head.next = null;  
        return  newHead;  
    }  
}