剑指offer题目15：反转链表

/**
* 题目15：反转链表
* 输入一个链表，反转链表后，输出新链表的表头。
*/

    @Test
    public void test15(){
        ListNode root=new ListNode(1);
        ListNode tmp=root;
        System.out.print("original List:  "+root.val+"\t");
        for(int i=2;i<6;i++){
            tmp.next=new ListNode(i);
            tmp=tmp.next;
            System.out.print(tmp.val+"\t");
        }
        root=ReverseList_15_3(root);
        System.out.print("\nreverse List:  ");
        while(root!=null){
            System.out.print(root.val+"\t");
            root=root.next;
        }
    }
    //解法1：使用3个指针进行反转
    //时间、空间复杂度O(n)、O(1)     22ms
    public ListNode ReverseList_15(ListNode head) {
        ListNode cur=head, pre=null ,next;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;//pre往后移一位
            cur=next;//cur往后移动一位
        }
        return pre;
    }
    //解法2：使用ArrayList来存储节点，然后遍历并反向      23ms
    //或者直接使用栈进行逆序
    public ListNode ReverseList_15_2(ListNode head) {
        if(head==null || head.next==null) return head;
        ArrayList<ListNode> arr=new ArrayList<>();//ctrl + alt + v自动补全左侧
        while(head!=null) {
            arr.add(head);
            head=head.next;
        }
        arr.get(0).next=null;
        for (int i = 1; i < arr.size(); i++) {
            arr.get(i).next=arr.get(i-1);
        }
        return arr.get(arr.size()-1);
    }
    //解法3：递归进行逆序，时间复杂度O(n)  18ms
    //将链表分为第一个节点head和剩余的节点rest，将剩余的节点rest反转，此时头指针rest指向原链表的末尾
    //通过head.next找到逆序后rest的尾部节点，因此head.next.next=head即可完全逆序，头指针依旧是rest
    public ListNode ReverseList_15_3(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode rest = ReverseList_15_3(head.next);
        head.next.next = head;
        head.next = null;
        return rest;
    }