链表翻转

前几天面试中提到了这个题目。虽然简单，可是写起来还是花了二十分钟，在这里记录一下。

题目说明

例如给定一个链表

1->2->3->4

翻转后返回

4->3->2->1

思路

稍微画图就可以很直观的想出链表翻转过程中，需要保存：
    上一个节点  （prev）
    当前节点    （cur）
    后继节点    （next）

代码

（迭代法）

public ListNode reverse(ListNode head){
    ListNode prev=null;
    ListNode next= head.next;
    while (next!=null){
        head.next=prev;
        prev=head;
        head=next;
        next=next.next;
    }
    head.next=prev;
    prev=head;
    return prev;
}

(迭代法优化)

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

(递归法)

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
            return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

(头插法)

public ListNode reverseList(ListNode head) {       
    ListNode kong=new ListNode(); 
    ListNode temp; 
    while (head!=null){ 
        temp=head.next;
        head.next=kong.next; 
        kong.next=head; head=temp; 
    } 
    return kong.next; 
}