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

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

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) {
}
// Recursive processing of subsequent nodes
// Local inversion node