35.翻转链表

/**
 * Definition of singly-linked-list:
 *
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

///递归方法
class Solution {
public:
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        // write your code here
        if(head == NULL || head->next == NULL) return head;//先将头节点与最后一个节点翻转
        
        ListNode* r = reverse(head->next);
        head->next->next = head;//头节点以外的节点所以是把next的和next.next的翻转
        head->next = NULL;//头节点被转到最后一位 下一个为null
        
        return r;

    }
};

///循环方法
class Solution {
public:
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        if (head == NULL) {
            return NULL;
        }
        ListNode *per = NULL, *cur = head, *net = head->next;
        while (net != NULL) {
            cur->next = per;
            per = cur;
            cur = net;
            net = cur->next;
        }
        cur->next = per;
        return cur;
    }
};