The title

Given a single linked list head pHead of length n, invert the list to return the new list head.

Data range: N \ LEQ1000N ≤1000< Requirements: Space complexity O(1)O(1), time complexity O(n)O(n).

For example, when the input linked list {1,2,3} is reversed, the original linked list becomes {3,2,1}, so the corresponding output is {3,2,1}. The above conversion process is shown in the figure below:

Example 1

Input: {1,2,3} return value: {3,2,1}

Example 2

Input: {} Returned value: {} Description: An empty linked list outputs nothing

describe

This is a question for beginners, use two ways to solve.

  • Single linked lists
  • Difficulty: one star

Formal method

  • Initialization: 3 Pointers
  1. The pre pointer points to the last node in the nullPTR list that has already been reversed
  2. Cur points to the first node in the list to be reversed, so the first node is to be reversed, so it points to head
  3. The nex pointer points to the second node of the list to be reversed. The purpose is to save the list, because when cur changes the pointer, the following list becomes invalid, so it needs to be saved
  • Next, loop through the following three actions
  1. Nex = cur->next
  2. Cur ->next = pre The next pointer to the first node of the unreversed list points to the last node of the reversed list
  3. Pre = cur, cur = nex; The pointer moves back to operate on the first node of the next unreversed list

The cyclic condition, of course, is cur! Nullptr = cur (cur); cur (cur);

/** * @author LaoTie * @project LaoTieTest * @date 2021/11/9 */

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; }}Copy the code
public static ListNode reverseList(ListNode head) {
  ListNode pre = null;
  ListNode cur = head;
  ListNode next = null;
  while(cur ! =null){
      next = cur.next;
      cur.next= pre;
      pre = cur;
      cur = next;
  }
  return pre;
}
Copy the code