# 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

## 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 ）

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 .
```/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {ListNode}
*/
const reverseList = (head) => {
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

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 .

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.
```/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {ListNode}
*/
const reverseList = (head) => {
//  Judge whether the current node still needs to process
}
//  Recursive processing of subsequent nodes
//  Local inversion node
};```

### 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

https://cdmana.com/2021/10/20211002145412980o.html

Scroll to Top