Reverse linked List (206)

This is a classic interview question, and it’s easy in LeetCode. As many people know, linked list or array questions should subconsciously reflect two information: double pointer, sentinel. The idea of double-pointers is similar to quicksort, where you use two Pointers to perform various operations in a linked list or array.

Without a sentry

This one also used sentinels and double Pointers. In fact, I was a little bit stubborn at first, thinking of using the double pointer without the sentry to see if I could write it. Although write out, but also took some time, because was inside a small pit to trip up. Here’s the hole I dug for myself

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode cur=head;
        ListNode next=cur.next;
        while(next!=null){
            ListNode tmpNext=next.next;
            next.next=cur;           
            cur=next;
            next=tmpNext;
        }
        return cur;
        
    }
}
Copy the code

The above code is not complicated: we declare two Pointers cur and next. Then we save next. Next in the loop, because we want to keep the loop going. Once saved, we can point next. Next to cur, which means that next points to the previous node. For example, we have the following linked list:

1 --> 2 --> 3 --> 4 -->5
|     |
cur   next
Copy the code

After executing the above two lines, the state is now as follows:

1 <-- 2     3 --> 4 -->5
|     |
cur   next
Copy the code

You can see that next of the 2 nodes already points to 1, which is exactly what we want. But now we’re done with node 2 and 3, so how do we go down? It doesn’t matter, because we use ListNode tmpNext= Next-next; The 3 nodes have been saved, so the loop can continue normally as follows:

cur=next;
next=tmpNext;
Copy the code

Run the above code and leetCode will tell you that there is a loop in the linked list. If the list has a loop, you will enter an infinite loop during traversal, just like JDK1.7 hashCode.

Why is that? As the observant reader may have noticed, pointing 2 nodes to 1 is fine, but 1 node still keeps a reference to 2. So what? Simply empty next on node 1. So I didn’t even think about changing it to the following code:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode cur=head;
        ListNode next=cur.next;
        while(next!=null){
            cur.next=null;
            ListNode tmpNext=next.next;
            next.next=cur;           
            cur=next;
            next=tmpNext;
        }
        return cur;
    }
}
Copy the code

Empty cur.next at the beginning of the loop, leaving everything else unchanged. Then happily submit the code, only for LeetCode to tell you that something went wrong:

Input: [1, 2, 3, 4, 5] Output [5, 4] Expected,4,3,2,1 [5]Copy the code

So it’s just 5,4 where are the 1,2,3? Why is that? How can I be so stupid that I can’t figure out such an easy question? OMG! I believe that people who brush the question have had this feeling, encounter a simple do not make two times to begin to doubt life! So what to do? Take a deep breath then try again (cur.next=null). This will cause the next loop to empty the cur.next that is already pointing to the correct position. All nodes before the penultimate are lost.

So how do you adjust that? Very simple, put cur.next=null outside the loop and execute it once. Modify the code as follows:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode cur=head;
        ListNode next=cur.next;
        cur.next=null;
        while(next!=null){
            ListNode tmpNext=next.next;
            next.next=cur;           
            cur=next;
            next=tmpNext;
        }
        return cur;
        
    }
}
Copy the code

As you can see from the above, this can be done without sentries. But by introducing complexity, you can make careless mistakes. So for comparison let’s look at the code that uses sentry

Use the sentry

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        while(cur != null){
            final ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}
Copy the code

We introduced the Pre as a sentinel, and the whole code was a lot cleaner! A simple comparison with no-sentry code:

  1. Without the sentries,curPoint to the first node,nextIt points to the second node, but you don’t know how many nodes this list is going to have, so you have to decideheadWhether is empty
  2. When the sentry is not introduced, the first loop needs to be convertedcur.nextEmpty, otherwise loops will appear inside the list. With the introduction of sentries, there is no need to distinguish whether it is the first cycle or not, and all nodes move in step. Because the sentinel node does not have a pointer to the next node, no additional null operation is required. So don’t be clever, and don’t look down upon the wisdom of our predecessors.

conclusion

We implement list inversion with no sentry and with sentry respectively, and analyze the advantages brought by introducing sentry. Of course, there are other methods, such as introducing a stack and using the properties of the stack to reverse the list, but this definitely adds spatial complexity. We’re after the ultimate code, you know!

Brushing is a painful and happy thing, especially at the beginning is really painful and painful. At this time must be calm, guard against arrogance and impetuosity, must stick to it according to their own rhythm, so there will be harvest.