Complete high-frequency question bank warehouse address: github.com/hzfe/awesom…

The full frequency question bank reading address: febook.hzfe.org/

Topic describes

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

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

Solution 1: Iteration (double pointer)

Links to online

This method is to traverse the linked list, and then change the direction of next when visiting each node to achieve the purpose of reversing the linked list.

  1. Initialize the cur and pre nodes, pointing to head and NULL, respectively.
  2. Loop through the linked list and declare the temp node to hold the next node of the current node.
  3. Change the next pointer to the current cur node to the pre node.
  4. Change the pre node to a CUR node.
  5. Change the cur node to temp.
  6. Continue processing until the cur node is null and the pre node is returned.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
const reverseList = (head) = > {
  let cur = head; // The head pointer to the forward list
  let pre = null; // The head pointer to the reverse list
  while (cur) {
    const temp = cur.next; // Hold the subsequent nodes of the current node to update the forward list
    cur.next = pre; // Point the current node to the reverse list. This is the process of establishing a back link
    pre = cur; // Update the head pointer of the reverse list to the currently processed node. The round of the reverse list is completed
    cur = temp; // Replace the forward list header pointer with a temporary node. The forward list processing is complete and the next round of processing begins
  }
  return pre;
};
Copy the code

Complexity analysis

  • Time complexity O(N) : Traversing lists uses linear size time.
  • Spatial complexity O(1) : The variables pre and cur use constant size for extra space.

Solution two: recursion

Links to online

When dealing with a list recursively, you start at the first node of the list, find the last node, which is the head of the reverse list, and go back.

  1. The head identifier of the initial linked list.
  2. Return head if head is empty or head.next is empty.
  3. Define the reverseHead node to hold the reversed list values.
  4. Each time, the next node of head points to head, creating a reversal.
  5. Recursive to the last node, return to the reverseHead.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
const reverseList = (head) = > {
  // Check whether the current node needs processing
  if (head == null || head.next == null) {
    return head;
  }
  // Recursively process subsequent nodes
  const reverseHead = reverseList(head.next);
  // local reverse node
  head.next.next = head;
  head.next = null;
  return reverseHead;
};
Copy the code

Complexity analysis:

  • Time complexity O(N) : N is the length of the linked list, which requires the inversion of each node in the list.
  • Spatial complexity O(N) : N is the length of the linked list. The spatial complexity depends mainly on the stack space of recursive calls, which is at most N layers.

The resources

  1. The sword refers to offer