链表反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

头插法：

public ListNode ReverseList(ListNode head) {
	ListNode cur = head;
	if(head!=null)
	{
		head=head.next;
		cur.next = null;
	}
	ListNode temp = head;
	while(head!=null)
	{
		head=head.next;
		temp.next = cur;
		cur = temp;
		temp = head;
	}
	return cur;
}

递归实现：

public ListNode ReverseList(ListNode head) {
	if(head == null || head.next == null)
	{
		return head;
	}
	ListNode temp = ReverseList(head.next);//当传入结点为空时，返回值存在temp中作为翻转链表的头结点。
	head.next.next=head;//从底层依次退出并对链表进行翻转
    head.next=null;
	return temp;
}

就地反转：

public ListNode ReverseList(ListNode head) {
		ListNode cur = null;//存储翻转后链表的头结点；
        ListNode tempNext = null;//存储翻转前链表的头结点的下一个结点，用于翻转前链表头结点的后移
        while(head!=null)
        {
            tempNext = head.next;//存储当前头结点的下一个结点。
            head.next = cur;//链表翻转。
            cur = head;//将翻转后链表的头指针前移。
            head=tempNext;//更新翻转前的头结点位置。
        }
    return cur;
}