The profile

This article introduces the basic knowledge of linked list structure, single linked list inversion. This knowledge point is also often used by companies as a starting point for examining algorithms and is also seen in the recent open source interview questions project. In fact, the previous article LeetCode advanced 226- flipped binary tree (Huawei interview questions) belong to the same series if you do not understand will be despised by the interviewer.

Reverse, such as ABCD to DCBA, can only search the list once.

The original problem

206. Reverse Linked List (Easy)

IReverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

206. Reverse linked lists. (simple)

Reverse a single linked list.

Example:

Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL advanced: you can use loops and recursive two ways to solve this problem?

  • Classification: Linked List

Analysis of the

Search only once, that is, the cycle time complexity O(n).

Concept design

As requested, the essential idea of reversing a linked list is to point the next pointer of each list node to the previous node.

Method one: recursion

At the heart of recursion is the idea of splitting one thing into recursive “big” things and practical “small” things. Ontology can imagine on macroscopic, the head quarter of the next node as a new chain table (can be simple to understand as a linked list is divided into head node and another “big” node, as shown in the figure below), so it split into three things 1, dealing with “big” node (new list), the inversion list recursively; 2. The pointer of the “large” node points to the head node in reverse order; 3. The pointer to the head node itself is reversed.

1And nulling of the head node2Declare that bigNode is assigned to the next node of the head node: head.next;3, recursively reverse processing "large" nodes (linked lists except head nodes);4, the pointer of the "large" node (the linked list except the head node) points to the previous node, that is, the head node;5The pointer to the head node points to null in reverse order (because the head node becomes the tail node after reverse order);6Return the "large" node, that is, the new linked list after the reverse order;Copy the code

Method 2: Loop (non-recursive)

In each loop, the next node of the current node points to the pre node of the previous node. The previous node needs to be recorded during the loop. The first node is the last node in the new list because of the inversion so the previous node of the first node is empty.

Pseudo code:

1Declare variable preNode to store the previous node;2,whileLoop until the last node of the list is reached; I. Declare the temp variable to store the next node of the current node. Ii. The current node points to the previous node. Iii. Update preNode to the current node after a single loop; Iiii. head is updated to move the head pointer to its next node after a single loop;3. At the end of the loop, return the last preNode assignment to the tail node, that is, the head node of the reverse list;Copy the code

Coding practices

The recursive implementation

   public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode bigNode = head.next;
        ListNode node = reverseList(bigNode);
        bigNode.next = head;
        head.next = null;
        return node;
    }
Copy the code

Cycle to achieve

    public ListNode reverseList(ListNode head) {
        ListNode preNode = null;
        while(head ! =null){
            ListNode temp = head.next;
            head.next = preNode;
            preNode = head;
            head = temp ;
        }
        return preNode;
    }
    
Copy the code

conclusion

The linked list in the Huawei interview is a basic knowledge question related to linked lists. The core of the question is to understand the Pointers of linked list nodes. If you found this article helpful, give it a thumbs up