[数据结构与算法]NC-反转链表

解法1. 哑节点前插

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode dummy = new ListNode(-1);
        while(head!=null){
            ListNode p = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = p;
        }
        return dummy.next;
    }
}

解法2. 递归
首先逐个节点拆分，然后每两个节点进行方向颠倒。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode reverseHead = ReverseList(head.next);
        head.next.next = head;
        head.next=null;
        return reverseHead;
    }
}