Java 【力扣206】反转链表（3种方法）

package seqlist.leetcode;
public class ListNode {
    int val;
    ListNode next;
    public ListNode(){
    }
    public ListNode(int val){
        this.val=val;
    }
    public ListNode(int val,ListNode next){
        this.val=val;
        this.next=next;
    }
}

package seqlist.leetcode;
//反转链表(回文)
public class Num206 {
    //方法1 头插
    public ListNode reverseList(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode dummyHead=new ListNode(-1);
        while (head!=null){
            ListNode node=new ListNode(head.val);
            node.next=dummyHead.next;
            dummyHead.next=node;
            head=head.next;
        }
        return dummyHead.next;
    }
    //方法2 原地移动
    public ListNode reverseList2(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode prev=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode node=cur.next;
            cur.next=prev;
            prev=cur;
            cur=node;
        }
        return prev;
    }
    //方法3 递归
    public ListNode reverseList3(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode sec=head.next;
        ListNode newHead=reverseList3(head.next);
        sec.next=head;
        head.next=null;
        return newHead;
    }
}