206. 反转链表

难度 easy

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路1：双指针迭代法，相对来说是很简单的，用两个指针new_head和head不断地向后移动，在移动的过程中改变指针指向即可。new_head首先初始化为null，然后head指向当前遍历到的节点，把下一个节点保存在t里，然后head的下一个节点赋为new_head，也就是head指向new_head，同时new_head赋为head，也就是new_head向head的方向前进一步，而head同样往下一个节点(也即是t）前进一步，直到head指向的节点为空，也就是链表末尾。

代码 t100 s74 java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode new_head = null;
        while(head!=null){
            ListNode t = head.next;
            head.next = new_head;
            new_head = head;
            head = t;            
        }
        return new_head;
    }
}

代码 cpp

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newhead  = NULL;
        while(head){
            ListNode *t = head->next;
            head->next = newhead;
            newhead = head;
            head = t;
        }
        return newhead;
    }
};

解题思路2：这道题还可用递归的解法，递归的解法比双指针难了一点，首先用一个helper函数，参数为pre和cur两个节点，pre初始化为null，cur初始化为head，如果cur为null，说明head为空，有可能是空链表也有可能是到了链表尾，此时返回pre，否则就用next保留head的下一个节点，同时改变指针指向，将cur指向pre，同时进入递归函数，把cur和next传进去，也就是相当于把cur赋给pre，next赋给cur，pre和cur都向链表尾移动了一位，在下一个递归函数里变成了cur和next。

代码 t100 s88 java

class Solution {
    public ListNode reverseList(ListNode head) {
        return helper(null, head);
    }

    public ListNode helper(ListNode pre, ListNode cur){
        if(cur==null) return pre;
        ListNode next = cur.next;
        cur.next = pre;
        return helper(cur, next);
    }
}

参考资料：
https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/

206. 反转链表

原文：https://www.cnblogs.com/zhengxch/p/14727758.html