LeetCode points to Offer 24. Reverse linked list

topic description

Define a function that takes as input the head node of a linked list, reverses the linked list and outputs the head node of the reversed linked list.

Sample

Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULL

Question link
https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/

Solution ideas

My idea for this question is to use the head insertion method, that is, each insertion is placed at the head node of the linked list, so that you can go backwards while inserting, and you don't need to maintain other variables, which is very suitable for this problem..

Complexity Analysis

Time complexity: O(n), where n is the length of the linked list.Need to traverse the linked list once.
Space complexity: O(1).

Code

Java code:

class Solution {public ListNode reverseList(ListNode head) {// This question uses tail insertionListNode myHead = new ListNode();while (head != null) {ListNode node = new ListNode(head.val);// Don't let the list breaknode.next = myHead.next;myHead.next = node;head = head.next;}// My head node here is empty, so return nextreturn myHead.next;}}