编程知识 cdmana.com

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

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

版权声明
本文为[HZFEStudio]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211002145412980o.html

Scroll to Top