LintCode 35: Reverse Linked List (最基本最经典的链表反转题)

关于链表反转有几种做法：
解法1：比较简洁，思路是把链表节点按prev-head-temp的顺序依次递增，直到最后的NULL。

/**
 * 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) {
        ListNode *prev = NULL;
        
        while(head) {
           ListNode *temp = head->next;
           head->next = prev;
           prev = head;
           head = temp;
        }
        
        return prev;
    }
};

解法2：3指针法。比较经典。
对比解法1可以知道两种方法等价：
p1 <-> prev
p2 <-> head
p3 <-> temp

class Solution {
public:
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        ListNode *p1, *p2, *p3;
        
        if (!head || !head->next) return head;
        
        p1 = head; 
        p2 = p1->next;
        
        while(p2) {
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        
        head->next = NULL;
        head = p1;
        return head;
    }
};

解法3：通过stack压栈来反转。
下次再做。

解法4：通过递归应该也可以。下次再做。