Two implementation methods of linked list inversion, the latter beat 100% of users!

Linked list inversion is a very basic but very popular algorithm interview question. It has also appeared in question 24 of sword finger offer. As for how hot it is, you can see from the list below.

According to the data of niuke.com, the interview questions of linked list inversion occupy the double lists of [last week's test] and [R & D favorite test] respectively. Well-known Internet companies such as Netease and byte have passed the test, but the passing rate is only 30%. Therefore, in this paper, we will learn the two implementation methods of reverse linked list.

subject

Title: Sword finger offer 24 Reverse linked list

Description: define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted linked list.

Example:

Leetcode link: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

Implementation method 1: stack

Stack all:

public ListNode reverseList(ListNode head) {
    if (head == null) return null;
    Stack<ListNode> stack = new Stack<>();
    stack.push(head); // 存入第一个节点
    while (head.next != null) {
        stack.push(head.next); // 存入其他节点
        head = head.next; // 指针移动的下一位
    }
    // 反转链表
    ListNode listNode = stack.pop(); // 反转第一个元素
    ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
    while (!stack.isEmpty()) {
        ListNode item = stack.pop(); // 当前节点
        lastNode.next = item;
        lastNode = item;
    }
    lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
    return listNode;
}

The leetcode verification results are shown in the following figure:

Implementation mode 2: recursion

public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 从下一个节点开始递归
    ListNode reverse = reverseList(head.next);
    head.next.next = head; // 设置下一个节点的 next 为当前节点
    head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
    return reverse;
}

The leetcode verification results are shown in the following figure: