Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Leetcode206 – Reverse linked list

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

Given the head node of a single linked list, reverse the list and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5] output: [5,4,3,2,1]

Input: head = [1,2] output: [2,1] example 3:

Input: head = [] Output: []

Analysis of the problem

Method 1

This scheme mainly adopts the idea of front and rear node replacement. At the end node in a recursive operation, the recursive operation moves forward from the end node. We’re going to do it recursively. You have to find the next node every time. The next node of the next node is set to the current node and the current next node of the next node is replaced with the previous node. Proceed in this way until the last node returns as the head node. The code is as follows:

public ListNode reverseList(ListNode head) { if(head == null){ return null; } // End node if(head.next == null){return head; }else{ ListNode node = reverseList(head.next); ListNode last = getNextNode(head); head.next = null; last.next = head; return node; } } public ListNode getNextNode(ListNode node){ if(node.next ! = null){ return getNextNode(node.next); }else{ return node; }}Copy the code

Method 2

This method is an optimization of the recursive method, which simplifies the processing steps in the recursive process and reduces the amount of code. The idea is also the associative replacement between two nodes. The code is as follows:

public ListNode reverseList(ListNode head) { if(head == null){ return null; } // End node if(head.next == null){return head; }else{ ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; }}Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (1)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.