题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

迭代解法

反转链表第一感觉，我们应该想到的是，把中间的指针连接，变成相反的，然后移动prev 和 curv就可以了，如下图

但是，当将指针连接反转时，中间的连接就断了，就没法移动了，出现下图所示的情况

此时，我们需要一个临时指针变量next，用来保存后一个节点，来帮助移动

递归解法

递 归
先 递 ，得到最后一个节点
再 归 ，通过 head.next.next = head 将最后一个节点的指针指向前一个
再 head.next = null 将原先后面的节点清空

代码

迭代解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curv = head;
        while(curv != null){
            ListNode next = curv.next;
            curv.next = prev;
            prev = curv;
            curv = next; 
        }
    return prev;
    }
}

递归解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 递归
    public ListNode reverseList(ListNode head) {
        // 终止条件
        if(head==null || head.next==null){
            return head;
        }
        //递到尾节点，反转的话，这个节点就是头节点，所以最后返回p
        ListNode p = reverseList(head.next);
        // 开始归
        // head与head.next之间 建立双向链
        head.next.next = head;
        // 删掉前向链，留下的就是上一步建立的反向链。反转成功
        head.next = null;
        return p;
    }
}