题目描述

给你单链表的头节点 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

一、解题思路

整体思路：使用头插法反转链表 解题思路： ①用 head 表示当前节点。如果 head 不为空，申请一个 dummy 结点，和一个p结点，令p = head.next; ②因为第一个结点反转之后便成为最后一个结点，head 一开始指向第一个结点，先将head.next = null;，再令dummy.next = head; ，此时链表被分成两个部分，一个是以dummy为首结点的已经反转的链表，和以p为首结点的未反转部分的链表。 ③如果p != null 首先，移动 head 和 p， 令head = p; p = p.next; 其次，头插法，令head.next = dummy.next; dummy.next = head; ④重复③直到p指针为空，相当于遍历结束。 ⑤返回dummy.next

二、代码

1.反转链表

代码如下：

class Solution {
          
   
    public ListNode reverseList(ListNode head) {
          
   
        if (head == null) {
          
   
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode p = head.next;
        head.next = null;
        dummy.next = head;
        while (p != null) {
          
   
            head = p;
            p = p.next;
            head.next = dummy.next;
            dummy.next = head;
        }
        return dummy.next;
    }
}

2.测试数据

代码如下：

public class ReverseList {
          
   
    public static void main(String[] args) {
          
   
        // 1
        int[] arr1 = {
          
   1, 2, 3, 4, 5};
        ListNode head1 = new ListNode(arr1);
        System.out.println(head1);
        System.out.println("==========反转后==========");
        ListNode reverseList1 = new Solution().reverseList(head1);
        System.out.println(reverseList1);
        System.out.println();
        // 2
        int[] arr2 = {
          
   1, 2};
        ListNode head2 = new ListNode(arr2);
        System.out.println(head2);
        System.out.println("==========反转后==========");
        ListNode reverseList2 = new Solution().reverseList(head2);
        System.out.println(reverseList2);
        System.out.println();
        // 3
        int[] arr3 = {
          
   };
        ListNode head3 = new ListNode(arr3);
        System.out.println(head3);
        System.out.println("==========反转后==========");
        ListNode reverseList3 = new Solution().reverseList(head3);
        System.out.println(reverseList3);
        System.out.println();
    }
}

3.复杂度分析

①时间复杂度：O(n) ②空间复杂度：O(1)

4.运行结果及执行时间