Leetcode exercise - 206 Reverse linked list

1. Title Description

206. Reverse a linked list

Here's the head node of the list head , Please reverse the list , And return the inverted linked list .

Example 1：

 Input ：head = [1,2,3,4,5]
 Output ：[5,4,3,2,1]

Example 2：

 Input ：head = [1,2]
 Output ：[2,1]

Example 3：

 Input ：head = []
 Output ：[]

2. Problem solving ideas and codes

2.1 Their thinking

This question is relatively simple , But it is also a very common topic in the interview . The title requires reversing the linked list , You can use the stack violently to solve , But this is not simple enough, and you can't get points in the face market , And you need to traverse twice . So use three reference variables pre、next、curr To refer to the previous node 、 Next node and current node . Begin to curr Point to Head node and traverse from the head node ,next Point to the next node of the current node , Then let the current node next Point to previous node , That is to say pre. Move back pre and curr, send pre Point to the current node curr , Current node curr Move back to next. Examples of topics below 1->2->3->4->5->NULL To illustrate ：

• First curr Point to the head node 1,pre and next Point to null;
• then next Point to curr The next node of 2;
• curr Of next Point to pre, also curr Move back to 2;
• Repeat the above steps , until curr Point to null, Return at this time pre Point to the node , That is, the inverted head node
  

2.2 Code

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if (head == null) {
    
            return null;
        }
        ListNode pre = null;
        ListNode next = null;
        ListNode curr = head;
        while (curr != null) {
    
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

2.3 test result

Pass the test

3. summary

• This is a very simple application in linked lists , Often appear in interviews
• Use pre、curr、next Three variables to complete the inversion , The whole process is not difficult, just sort out the ideas clearly
• This problem is related to The finger of the sword Offer 24. Reverse a linked list identical