This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Reverse a linked list

Given the head node of a single linked list, reverse the list and return the reversed list.

Second, train of thought analysis

  • A normal operation of a linked list is to iterate through the list to perform operations. The Leetcode website also gives us a hint that inversion can be achieved through iteration and recursion.
  • Let’s examine the implementation logic in two ways

The iteration

  • First of all, we need to use three independent nodes to complete the operation of iteration inversion. , respectively,preNode.nextNode.currentNode. They are used to represent the front node, back node, and current node respectively.
  • Let’s use animation to explain how the two adjacent nodes rely on these three nodes to achieve inversion

  • This is how two or two nodes operate. At the end of the operation, preNode is the last node in our original list. After the inversion, it is exactly the beginning of the list, so we just return preNode
public ListNode reverseList(ListNode head) {
    ListNode preNode = null;
    ListNode nextNode = null;
    ListNode currentNode = head;
    while(currentNode ! =null) {
        nextNode = currentNode.next;
        currentNode.next = preNode;
        preNode = currentNode;
        currentNode = nextNode;
    }
    return preNode;
}
Copy the code
  • Principle + code smells better. Let’s go straight to Leetcode and run our test cases

  • The result is perfect, execution speed is up to the ceiling, memory consumption is not too low 90% which I think is excellent.

recursive

  • Recursion should be better understood. Recursion is to go to the bottom and start executing. Recursion and iteration are executed in opposite directions.

  • The recursion finally executes the neighboring nodes on the right first. All you need to do is point two Pointers to the change. Recursion is the most convenient. But the performance is not as high as iteration
public ListNode reverseList(ListNode head) {
    if (head == null) {
        return head;
    }
    return digui(head, head.next);
}

public ListNode digui(ListNode preNode , ListNode head) {
    if (head == null) {
        return preNode;
    }
    ListNode diguiNode = digui(head, head.next);
    head.next = preNode;
    preNode.next=null;
    return diguiNode;
}
Copy the code

Four,

  • Often the simplest mental performance is not the best.
  • Auxiliary nodes are necessary in the operation of linked lists. Often we need secondary nodes to temporarily store the switch nodes

Thumb up!!!!