Linked list inversion implementation method, the latter beat 100% of users!

Linked list inversion is a very basic but very popular algorithmic interview question, it also appeared in "Sword Finger Off" question 24, as to how hot it (door) look at the list below.

From the data of Niu guest network, the chain table reversal interview questions respectively occupied the double list of "last week's examination" and "research and development favorite test", such as NetEase, byte and other well-known Internet companies have been tested, but the pass rate is low only 30%, so this article we will learn the two implementation methods of reversing the linked list.

Leaderboard data: https://www.nowcoder.com/activity/oj

topic

Title: Sword refers to Offer 24. Reverse the list

Description: Define a function that enters the head node of a list, reverses the list, and outputs the head node of the reversed list.

example:

Enter: 1->2->3->4->5-> NULL

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

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

Implementation one: Stack

All in:

Because the stack is an advanced, post-out data structure, it executes as follows:

The final result of execution is shown in the following image:

The implementation code looks like this:

public ListNode reverseList(ListNode head) {
    if (head == null) return null;
    Stack 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 validation results are shown in the following image:

Implementation mode two: recursive

The implementation code looks like this:

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 validation results are shown in the following image:

summary

In this paper, we use Stack and recursive methods to implement the function of list inversion, in which Stack is implemented by taking advantage of the stack-in, first-out features can be directly reversed to the list, the implementation of ideas and implementation code are relatively simple, but in terms of performance and memory consumption are not ideal, can be used as a written test of the bottom implementation scheme;

This article is from the public number: Java Chinese community, author: Lei brother

Above is W3Cschool编程狮 about the link list reversal implementation method, the latter beat 100% of users! Related to the introduction, I hope to help you.