preface

These two days in the cattle online list this algorithm problem, a hard battle summed up is those routines, as long as you know some common routines, encountered a list of algorithms will have a general idea. The full text contains the following routines:

  • How fast a pointer
  • The linked list deletes nodes
  • List inversion
  • Temporary head node
  • Destroy the current node

But there are a few small details that you need to find yourself in the process of doing the problem, and here are just a few more common routines that I hope will help you.

How fast a pointer

The fast pointer is set to slow and fast. The first pointer moves one step at a time and the second pointer moves two steps at a time. The number of moving steps is not certain, can be decided according to the actual situation

Find the middle node of the list

The fast pointer moves two steps at a time, while the slow pointer moves one step at a time.

ListNode fast = head;
ListNode slow = head;
while(slow.next ! =null&& fast.next ! =null&& fast.next.next ! =null) {
    fast = fast.next.next;
    slow = slow.next;
}
ListNode mid = fast.next == null ? slow : slow.next; // Even <-> odd
Copy the code

Find the penultimate KTH node

The fast pointer first moves K steps and then reaches the end with the slow pointer.

ListNode fast = pHead;
ListNode slow = pHead;
while (k-- < 0) {
	if (fast == null) { // The length is greater than the list length
	    return null;
	}
    fast = fast.next;
}

while(fast ! =null) {
    fast = fast.next;
    slow = slow.next;
}

return slow;
Copy the code

The linked list deletes nodes

Deleting the current Node

I don’t have to say anything about this, just record the previous node.

ListNode pre = slow;
while(fast ! =null) {
    fast = fast.next;
    pre = slow;
    slow = slow.next;
}
pre.next = slow.next;
Copy the code

Delete the next node

ListNode cur = head;
while(cur.next ! =null) {
    if (cur.val == cur.next.val) {
        cur.next = cur.next.next; // If the values are the same, you only need to change the location of the next node
    } else{ cur = cur.next; }}Copy the code

Reverse a linked list

Enter a linked list, reverse the list, output the new list header.

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode ret = null;
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null; // The previous node
        ListNode next = null; // Next node
        while(head ! =null) {
            next = head.next;
            head.next = pre; // The next node of the current node is denoted as the previous node -> reverse
            pre = head;
            head = next;
        }
        returnpre; }}Copy the code

Temporary head node

Removes duplicate elements from the linked list

By setting up a temporary head node, you can make things much easier when you need to process a head node.

public ListNode deleteDuplicates (ListNode head) {
    ListNode sign = new ListNode(1); // Define a temporary head node to act as the previous node
    sign.next = head;
    
    ListNode pre = sign;
    ListNode cur = head;
    while(cur ! =null&& cur.next ! =null) {
        if (cur.val == cur.next.val) {
            ListNode tmp = cur.next;
            while(tmp ! =null && cur.val == tmp.val) {
                tmp = tmp.next;
            }
            pre.next = tmp;
            cur = tmp;
        } else{ pre = pre.next; cur = cur.next; }}return sign.next;
}
Copy the code

Destroy the current node

The idea of destroying the current node is very simple to determine whether there is a ring in the linked list. At the same time, the space complexity is O(1), but the disadvantage is that it will destroy the continuity of the linked list. If the problem requires that nodes not be destroyed, then the fast or slow pointer can also be used to determine whether there is a ring.

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    if (head.next == head) { // It encounters a broken node, that is, the node that was originally looped into the list
        return true;
    }
    ListNode nextNode = head.next;
    head.next = head; // Break the node
    return hasCycle(nextNode);
}
Copy the code

conclusion

1. Memorize common routines and digest them as your own knowledge. 2, when the problem do not panic, calm analysis, you can first draw the basic idea of solving the problem on paper, and then handwritten code. 3. Don’t be happy if you pass the check. Instead, you should look at the differences between others’ ideas and yours, and then think about whether there are opportunities for improvement in your own ideas. 4, there is no detailed algorithm process here, but the author hopes that you can experience the secret of the algorithm after learning the routine. Learning is endless, algorithm is waiting for you to break.

Personal note

The contents of this blog are all notes made by the author to learn, invade and delete! If used for other purposes, please specify the source!