Leetcode：206 反转链表

迭代方法：从前往后

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode list) {
        ListNode newList=null;
        while(list!=null){
            ListNode temp=new ListNode(list.val);
            temp.next=newList;
            newList=temp;
            if(list.next!=null)list=list.next;
            else break;
        }
        return newList;
    }
}

减少空间复杂度 O(1)不新建节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* result=NULL,*tmp=NULL;
        while(head!=NULL){
            tmp=result;
            result=head;
            head=head->next;
            result->next=tmp;
        }
        return result;
    }
};

递归方法：从后往前，注意链表成环，注意边界条件

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None:
            return None
        if head.next==None:
            return head
        else:
            newHead=self.reverseList(head.next)
            head.next.next=head
            head.next=None
        return newHead