206. Reverse linked list (linked list)

The question ： Invert a single chain table .

Example : Input : 1->2->3->4->5->NULL Output : 5->4->3->2->1->NULL

Method 1 ： Double finger needling

public class Fanzhuanlianbiao {
    static class ListNode{
        int val;// data ： Node data 
        ListNode next;// object , Reference next data object 

        // Construction method of linked list class 
        ListNode(int val){
            this.val = val;
        }
    }
    public void print (ListNode head){
        while(head!=null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
    public ListNode reverseList(ListNode head){
        // Define a temporary variable to save the next node of the current node 
        ListNode temp;
        // Define the precursor node 
        ListNode pre = null;
        // Define the current node 
        ListNode cur = head;
        while(cur!=null){
            // The temporary variable records the next node of the current node 
            temp=cur.next;
            // The current node points to the predecessor node 
            cur.next = pre;
            // The precursor node moves back one bit 
            pre = cur;
            // Move the current node back one bit 
            cur = temp;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Fanzhuanlianbiao fanzhuanlianbiao = new Fanzhuanlianbiao();
        ListNode node = node1;
        fanzhuanlianbiao.print(node);
        System.out.println();

        ListNode res =fanzhuanlianbiao.reverseList(node1);
        fanzhuanlianbiao.print(res);
    }
}

Output results ：

12345

54321 

Method 2 ： Recursive method

The idea is similar to double pointer , Pay attention to the end of recursion and recursive variables

// Recursive method 
    public ListNode reverseList(ListNode head){
        return reverse(null,head);
    }
    private ListNode reverse(ListNode pre,ListNode cur){
        // Recursive end point reached , return pre
        if (cur==null){
            return pre;
        }
        // Define temporary nodes temp Save the current node and the next node 
        ListNode temp = null;
        temp = cur.next;
        // reverse ( Current node refers to the forward node 
        cur.next = pre;
        return reverse(cur,temp);
    }