[数据结构与算法]力扣 206.反转链表（Java）

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
链接: 原题链接.

解题思路

一、三个节点倒

三个节点来回倒，手动模拟实现反转链表。
newHead：反转后链表的头节点
cur：当前链表的头节点
next：cur.next，改变cur.next指向后，还能通过next将cur更新为当前链表的头节点。

/**
 * 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)    return head;
        ListNode newHead = null,cur = head,next = cur.next;
        while(cur != null){
            //当前指向的不是空节点
            cur.next = newHead;
            newHead = cur;
            cur = next;
            if(cur != null)
            	//保证不会对空进行操作
                next = cur.next;
        }
        return newHead;
    }
}

该方法可自行画图，便于理解。

二、递归方法

/**
 * 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 || head.next == null){
            //只有一个节点或没有节点时  反转为它本身
            return head;
        }
        ListNode tail = head.next;
        ListNode p = reverseList(head.next);
        //反转两个节点
        head.next = tail.next;
        tail.next = head;
        return p;
    }
}

三、头插

分享翻到的一个比较简洁且好理解的方法：

/**
 * 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 ans = null;
        for (ListNode x = head; x != null; x = x.next) {
            ans = new ListNode(x.val,ans);
        }
        return ans;
    }
}