206.反转链表——学习笔记-526互联

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题目来源：力扣（LeetCode）链接

题解：

自己做的方法

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) { //如果链表为null，则直接返回null
            return head;
        }
        ListNode listNode = head.next;//把头节点的下一个节点保存
        ListNode newNode = head;//把头节点保存为新的节点，作为新链表的尾结点
        newNode.next = null;//把新节点的next置null
        while (listNode != null) {//如果listNode为空，说明到达链表的末尾
            ListNode nextNode = listNode.next;//保存当前节点的下一节点
            listNode.next = newNode;//把当前节点的next指向前一节点，实现反转
            newNode = listNode;//新节点后移
            listNode = nextNode;//当前节点后移
        }
        return newNode;//while循环结束后newNode就是反转后的头节点
    }
}

双指针法(跟自己想的方法类似，但是别人定义的变量更清晰)

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode preNode = null;//perNode表示前一节点
        ListNode curNode = head;//curNode表示当前节点
        ListNode tempNode = null;//tempNode表示临时节点
        while (curNode != null) {//curNode == null时，说明到达链表的最后
            tempNode = curNode.next;//把当前节点的下一节点保存下来
            curNode.next = preNode;//实现反转
            preNode = curNode;//节点后移
            curNode = tempNode;//节点后移
        }
        return preNode;//返回头节点
    }
}

递归法

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }
    //定义一个反转的方法
    public ListNode reverse (ListNode prev, ListNode cur) {
        if (cur == null) {//头节点为null或者到达链表的末尾，就返回前一节点
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;//临时保存当前节点的下一节点
        cur.next = prev;//实现反转
        return reverse(cur, temp);//把cur->pre temp->cur，后移节点进入递归
    }
}