Reverse one-way linked lists

Given the head node head of the single linked list, reverse the linked list, as shown in the figure:

Figure 1: single-linked list inversion effect demonstration

I have not read algorithms at ordinary times, only the concept of linked lists have a basic understanding. Seeing this topic, it is not difficult to feel. But to write about it, it’s still a bit of a brain drain.

The first time I did this topic, the code was not simple, and it took more than 20 minutes to get the correct conclusion after repeated debugging in IDEA.

Linked list class algorithm, pointer switching, always let a person dizzy… I don’t know if you feel the same way.

Try to problem solving

Here’s the code for my first attempt at solving the problem:

public static ListNode reverseList(ListNode head) { // 0. Determine the list is empty or only one element, don't need to reverse the if (head = = null | | head. The next = = null) {return head; } ListNode pre = head; ListNode next = pre.next; ListNode temp; while(next ! = null){// 1. Temp = Next-next; // 2. Next. Next = pre; If (temp == null){break; } // 4. Next = next; // set temp as next next = temp; } next = null;} next = null; Return next; // return next; }Copy the code

Okay, I’ll admit that my first solution was based on my feelings, and it was a bit of a thrill ride, and it took me eight steps. But the result came anyway.

Reflection & error correction

First of all, praise yourself and do the judgment of the exception case, that is, judge the null node and only one node

/ / 0. Judge list is empty or only one element, not reverse the if (head = = null | | head. The next = = null) {return head; }Copy the code

After the code masturbation, the feeling is not right, seems to take a lot of detours. How could one simple logic write so many lines of code! So many steps!

And then… Lost in thought…

The first question, which I quickly figured out, is why should I say break in a while loop if it says break?

Here’s what I thought at the time:

If you move the pointer around, next is the last node and returns. If you break without an if, next is always Null because next = temp. So why not return pre? I quickly changed a version, the code is much simpler.

public static ListNode reverseList(ListNode head) { // 0. Determine the list is empty or only one element, don't need to reverse the if (head = = null | | head. The next = = null) {return head; } ListNode pre = head; ListNode next = pre.next; ListNode temp; while(next ! = null){// 1. Temp = Next-next; // 2. Next. Next = pre; // 3. // 4. Next = temp; } next = null;} next = null; // 6. Return next as the return value. }Copy the code

Missing a step from the original version, but always feeling redundant step 5? Why add a special handler at the end? Head. Next = null.

Being is reasonable, but reasonable is not necessarily concise.

In order to see the process of pointer change and variable change more clearly, I decided to use the diagram to simulate the dynamic change process of this code pointer:

There's not enough brain space. Please understand that I'm picturing...

Single-linked list with 4 nodes:

Figure 2: The first loop completes step 2

Figure 3: The second loop completes step 2

Figure 4: The third loop completes step 2

Figure 5: End of loop, step 5 is completed

If you are careful, you must have found a very bad place, the 1->2 pointer has been unspeakably unreasonable, and needs to be manually cleared after the loop ends.

Once again on reflection…

My first pre started from node1, what if we started pre from null?

The concept of sentry came to mind in a section of Geek Time’s Beauty of Data Structures and Algorithms list.

Turn the book…

Sentinels solve border problems between countries. That seems kind of interesting. Try starting pre from null and next from Node1?

Crackle, rework the code:

public static ListNode reverseList(ListNode head) { // 0. Determine the list is empty or only one element, don't need to reverse the if (head = = null | | head. The next = = null) {return head; } ListNode pre = null; ListNode next = head; ListNode temp; while(next ! = null){// 1. Temp = Next-next; // 2. Next. Next = pre; // 3. // 4. Next = temp; } // 5. Return next as return value return pre; }Copy the code

The code has been reduced from 8 to 6 steps, and the reduction of these two steps is indeed a self-inflicted detour.

It seems that there is no room for further optimization of the code, and these lines of code are my first glimpse into the problems of dynamic programming.

Write in the last

The concept of linked list is easy to understand, but the implementation of algorithm often brings some complexity due to the movement of Pointers. Very easy to burn the brain, may also be split, ha ha ha ~, but there are tricks.

You can also try to solve the problem along my lines.

  • The first step in accordance with their own ideas to achieve
  • Step two: Find what you think doesn’t make sense
  • Optimization problem, summary

Here’s my summary:

  1. The node returning to the list can be the first node before the last node to avoid judging break again in the loop
  2. You can act as a special sentinel at the pre-processing node (or the end-of-processing node), reducing redundant code
  3. The critical points for processing must be carefully considered to avoid anomalies.

Algorithms are still very interesting, let’s see you in the sea of algorithms!

I’m Kazz of interview cycle, visit interview cycle website to download unlimited free information! Welcome to add the public account to discuss: