One of the most high-frequency algorithm problems in the front end! Reverse linked list

HZFEStudio 2021-10-14 04:09:13

Complete high frequency question bank warehouse address :https://github.com/hzfe/awesome-interview

Complete high frequency question bank reading address :https://febook.hzfe.org/

Title Description

Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list .

Example :

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

Solution 1 : iteration ( Double pointer )

Online links

This method is to traverse the linked list , Then, when accessing each node, modify next The direction of , Achieve the purpose of reversing the linked list .

  1. initialization cur and pre Two nodes , Point to respectively head and null.
  2. Cycle the linked list , Statement temp Node is used to save the next node of the current node .
  3. Modify the current node cur Of next The pointer points to pre node .
  4. pre Node is modified to cur node .
  5. cur Node is modified to temp node .
  6. Continue processing , until cur The node is null, return pre node .
/**
* 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 of the forward linked list 
let pre = null; // The head pointer of the reverse linked list 
while (cur) {
const temp = cur.next; // Staging subsequent nodes of the current node , Used to update the forward linked list 
cur.next = pre; // Point the current node to the reverse linked list , This is a process of establishing reverse links 
pre = cur; // Update the header pointer of the reverse linked list to the currently processed node , The construction of this round of reverse linked list is completed 
cur = temp; // Replace the forward chain header pointer with the temporary node , Forward linked list processing completed , Start the next round of processing 
}
return pre;
};

Complexity analysis

  • Time complexity O(N): Traversing the linked list uses linear size time .
  • Spatial complexity O(1): Variable pre and cur Use constant size for extra space .

Solution 2 : recursive

Online links

When using recursion to process linked lists , Start from the first node of the linked list , Then find the last node , This node is the head node of the inverted linked list , Then perform backtracking processing .

  1. The head node of the initial linked list ,head identification .
  2. If head Empty or head.next It's empty , return head.
  3. Definition reverseHead node , Save the inverted linked list value .
  4. Every time you let head Of the next node next Point to head, Form inversion .
  5. Recursive processing to the last node , return reverseHead.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
const reverseList = (head) => {
// Judge whether the current node still needs to process 
if (head == null || head.next == null) {
return head;
}
// Recursive processing of subsequent nodes 
const reverseHead = reverseList(head.next);
// Local inversion node 
head.next.next = head;
head.next = null;
return reverseHead;
};

Complexity analysis :

  • Time complexity O(N):n It's the length of the list , You need to reverse each node of the linked list .
  • Spatial complexity O(N):n It's the length of the list , The space complexity mainly depends on the stack space of recursive calls , At most n layer .

Reference material

  1. The finger of the sword offer
Please bring the original link to reprint ,thank
Similar articles